leetcode-BinaryTree
leetcode-BinaryTree
Tony Cao二叉树问题
递归问题常用的解题方法
确定递归函数的参数和返回值：
确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。确定终止条件：
写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。确定单层递归的逻辑：
确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
二叉树的分类
二叉树类型 定义 特点 普通二叉树 每个节点最多有两个子节点，分别是左子节点和右子节点 最基础的二叉树结构 满二叉树 每个节点要么没有子节点，要么有两个子节点 所有节点要么是叶节点，要么有两个子节点 完全二叉树 除了最后一层节点可能不满，其余每一层节点都是满的，并且最后一层的节点都是从左到右排列的 最后一层节点从左到右排列 完美二叉树 每一层的节点数都达到最大值的二叉树 所有叶节点都在同一层，每个内部节点都有两个子节点 平衡二叉树 任意节点的左子树和右子树的高度差不超过1 高度平衡，通过旋转操作维护 二叉搜索树 每个节点的左子树的所有节点值小于该节点值，右子树的所有节点值大于该节点值 用于高效搜索、插入和删除操作 AVL树 一种严格平衡的二叉搜索树，即任意节点的两个子树的高度差最多为1 严格平衡，通过旋转操作维护 红黑树 一种平衡二叉搜索树，每个节点都有颜色属性（红或黑），通过一组规则保持树的平衡 平衡性较弱于AVL树，但插入和删除操作更高效 堆 一种特殊的二叉树，分为最大堆和最小堆。最大堆每个节点的值大于等于其子节点的值，最小堆则相反 用于实现优先队列 霍夫曼树 用于数据压缩的二叉树，频率较高的字符被分配较短的编码，频率较低的字符被分配较长的编码 数据压缩 二叉树的遍历问题
通用模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31# BFS使用队列，把每个还没有搜索到的点依次放入队列，然后再弹出队列的头部元素当做当前遍历点
# 不需要确定当前遍历到了哪一层
while queue 不空：
cur = queue.pop()
for 节点 in cur的所有相邻节点：
if 该节点有效且未访问过：
queue.push(该节点)
# --------------------------------------------------------------
# 需要确定当前遍历到了哪一层
level = 0
while queue 不空：
size = queue.size()
while (size --) {
cur = queue.pop()
for 节点 in cur的所有相邻节点：
if 该节点有效且未被访问过：
queue.push(该节点)
}
level ++;
# DFS
result = []
def traversal(root: TreeNode):
nonlocal result
if root is None:
return
result.append(root.val) # 中
traversal(root.left) # 左
traversal(root.right) # 右迭代法【BFS】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61# 前序遍历-迭代-LC144_二叉树的前序遍历
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
# 根结点为空则返回空列表
if not root:
return []
stack = [root]
result = []
while stack:
node = stack.pop()
# 中结点先处理
result.append(node.val)
# 右孩子先入栈
if node.right:
stack.append(node.right)
# 左孩子后入栈
if node.left:
stack.append(node.left)
return result
# 中序遍历-迭代-LC94_二叉树的中序遍历
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
stack = [] # 不能提前将root结点加入stack中
result = []
cur = root
while cur or stack:
# 先迭代访问最底层的左子树结点
if cur:
stack.append(cur)
cur = cur.left
# 到达最左结点后处理栈顶结点
else:
cur = stack.pop()
result.append(cur.val)
# 取栈顶元素右结点
cur = cur.right
return result
# 后序遍历-迭代-LC145_二叉树的后序遍历
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
stack = [root]
result = []
while stack:
node = stack.pop()
# 中结点先处理
result.append(node.val)
# 左孩子先入栈
if node.left:
stack.append(node.left)
# 右孩子后入栈
if node.right:
stack.append(node.right)
# 将最终的数组翻转
return result[::-1]层序遍历模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root: return []
stack = [root] # 用来存储每层的 node
res = [] # 用来存储最后的结果
while stack:
size = len(stack) # 用来标记每层在stack的位置
temp= [] # 用来存储每层的 value
for i in range(size):
cur = stack.pop(0)
temp.append(cur.val)
if cur.left:
stack.append(cur.left)
if cur.right:
stack.append(cur.right)
res.append(temp)
return res递归法【DFS】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46# 前序遍历-递归-LC144_二叉树的前序遍历
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
# 保存结果
result = []
def traversal(root: TreeNode):
if root is None:
return
result.append(root.val) # 中
traversal(root.left) # 左
traversal(root.right) # 右
traversal(root)
return result
# 中序遍历-递归-LC94_二叉树的中序遍历
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
result = []
def traversal(root: TreeNode):
if root is None:
return
traversal(root.left) # 左
result.append(root.val) # 中
traversal(root.right) # 右
traversal(root)
return result
# 后序遍历-递归-LC145_二叉树的后序遍历
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
result = []
def traversal(root: TreeNode):
if root is None:
return
traversal(root.left) # 左
traversal(root.right) # 右
result.append(root.val) # 中
traversal(root)
return result
常见的二叉树问题模板
