前序遍历：先访问根节点，再前序遍历左子树，再前序遍历右子树
中序遍历：先中序遍历左子树，再访问根节点，再中序遍历右子树
后序遍历：先后序遍历左子树，再后序遍历右子树，再访问根节点
注意点
- 递归实现二叉树遍历非常简单，不同顺序区别仅在于访问父结点顺序
def preorder_rec(root):
if root is None:
return
visit(root)
preorder_rec(root.left)
preorder_rec(root.right)
return
def inorder_rec(root):
if root is None:
return
inorder_rec(root.left)
visit(root)
inorder_rec(root.right)
return
def postorder_rec(root):
if root is None:
return
postorder_rec(root.left)
postorder_rec(root.right)
visit(root)
return
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
preorder = []
if root is None:
return preorder
s = [root]
while len(s) > 0:
node = s.pop()
preorder.append(node.val)
if node.right is not None:
s.append(node.right)
if node.left is not None:
s.append(node.left)
return preorder
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
s, inorder = [], []
node = root
while len(s) > 0 or node is not None:
if node is not None:
s.append(node)
node = node.left
else:
node = s.pop()
inorder.append(node.val)
node = node.right
return inorder
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
s, postorder = [], []
node, last_visit = root, None
while len(s) > 0 or node is not None:
if node is not None:
s.append(node)
node = node.left
else:
peek = s[-1]
if peek.right is not None and last_visit != peek.right:
node = peek.right
else:
last_visit = s.pop()
postorder.append(last_visit.val)
return postorder
注意点
DFS 深度搜索-从下向上（分治法）
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
if root is None:
return []
left_result = self.preorderTraversal(root.left)
right_result = self.preorderTraversal(root.right)
return [root.val] + left_result + right_result
注意点：
DFS 深度搜索（从上到下） 和分治法区别：前者一般将最终结果通过指针参数传入，后者一般递归返回结果最后合并
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
levels = []
if root is None:
return levels
bfs = collections.deque([root])
while len(bfs) > 0:
levels.append([])
level_size = len(bfs)
for _ in range(level_size):
node = bfs.popleft()
levels[-1].append(node.val)
if node.left is not None:
bfs.append(node.left)
if node.right is not None:
bfs.append(node.right)
return levels
先分别处理局部，再合并结果
适用场景
分治法模板
给定一个二叉树，找出其最大深度。
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if root is None:
return 0
return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
class Solution:
def maxDepth(self, root: TreeNode) -> List[List[int]]:
depth = 0
if root is None:
return depth
bfs = collections.deque([root])
while len(bfs) > 0:
depth += 1
level_size = len(bfs)
for _ in range(level_size):
node = bfs.popleft()
if node.left is not None:
bfs.append(node.left)
if node.right is not None:
bfs.append(node.right)
return depth
给定一个二叉树，判断它是否是高度平衡的二叉树。
- 思路 1：分治法，左边平衡 && 右边平衡 && 左右两边高度 <= 1，
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
def depth(root):
if root is None:
return 0, True
dl, bl = depth(root.left)
dr, br = depth(root.right)
return max(dl, dr) + 1, bl and br and abs(dl - dr) < 2
_, out = depth(root)
return out
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
s = [[TreeNode(), -1, -1]]
node, last = root, None
while len(s) > 1 or node is not None:
if node is not None:
s.append([node, -1, -1])
node = node.left
if node is None:
s[-1][1] = 0
else:
peek = s[-1][0]
if peek.right is not None and last != peek.right:
node = peek.right
else:
if peek.right is None:
s[-1][2] = 0
last, dl, dr = s.pop()
if abs(dl - dr) > 1:
return False
d = max(dl, dr) + 1
if s[-1][1] == -1:
s[-1][1] = d
else:
s[-1][2] = d
return True
给定一个非空二叉树，返回其最大路径和。
- 思路：分治法。最大路径的可能情况：左子树的最大路径，右子树的最大路径，或通过根结点的最大路径。其中通过根结点的最大路径值等于以左子树根结点为端点的最大路径值加以右子树根结点为端点的最大路径值再加上根结点值，这里还要考虑有负值的情况即负值路径需要丢弃不取。
class Solution:
def maxPathSum(self, root: TreeNode) -> int:
self.maxPath = float('-inf')
def largest_path_ends_at(node):
if node is None:
return float('-inf')
e_l = largest_path_ends_at(node.left)
e_r = largest_path_ends_at(node.right)
self.maxPath = max(self.maxPath, node.val + max(0, e_l) + max(0, e_r), e_l, e_r)
return node.val + max(e_l, e_r, 0)
largest_path_ends_at(root)
return self.maxPath
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
- 思路：分治法，有左子树的公共祖先或者有右子树的公共祖先，就返回子树的祖先，否则返回根节点
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if root is None:
return None
if root == p or root == q:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left is not None and right is not None:
return root
elif left is not None:
return left
elif right is not None:
return right
else:
return None
给定一个二叉树，返回其节点值的锯齿形层次遍历。Z 字形遍历
class Solution:
def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
levels = []
if root is None:
return levels
s = collections.deque([root])
start_from_left = True
while len(s) > 0:
levels.append([])
level_size = len(s)
if start_from_left:
for _ in range(level_size):
node = s.popleft()
levels[-1].append(node.val)
if node.left is not None:
s.append(node.left)
if node.right is not None:
s.append(node.right)
else:
for _ in range(level_size):
node = s.pop()
levels[-1].append(node.val)
if node.right is not None:
s.appendleft(node.right)
if node.left is not None:
s.appendleft(node.left)
start_from_left = not start_from_left
return levels
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
if root is None: return True
def valid_min_max(node):
isValid = True
if node.left is not None:
l_isValid, l_min, l_max = valid_min_max(node.left)
isValid = isValid and node.val > l_max
else:
l_isValid, l_min = True, node.val
if node.right is not None:
r_isValid, r_min, r_max = valid_min_max(node.right)
isValid = isValid and node.val < r_min
else:
r_isValid, r_max = True, node.val
return l_isValid and r_isValid and isValid, l_min, r_max
return valid_min_max(root)[0]
- 思路 3：利用二叉搜索树的性质，根结点为左子树的右边界，右子树的左边界，使用先序遍历自顶向下更新左右子树的边界并检查是否合法，迭代版本实现简单且可以提前返回结果。
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
if root is None:
return True
s = [(root, float('-inf'), float('inf'))]
while len(s) > 0:
node, low, up = s.pop()
if node.left is not None:
if node.left.val <= low or node.left.val >= node.val:
return False
s.append((node.left, low, node.val))
if node.right is not None:
if node.right.val <= node.val or node.right.val >= up:
return False
s.append((node.right, node.val, up))
return True
给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。
- 思路：如果只是为了完成任务则找到最后一个叶子节点满足插入条件即可。但此题深挖可以涉及到如何插入并维持平衡二叉搜索树的问题，并不适合初学者。
class Solution:
def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
if root is None:
return TreeNode(val)
node = root
while True:
if val > node.val:
if node.right is None:
node.right = TreeNode(val)
return root
else:
node = node.right
else:
if node.left is None:
node.left = TreeNode(val)
return root
else:
node = node.left
- 掌握二叉树递归与非递归遍历
- 理解 DFS 前序遍历与分治法
- 理解 BFS 层次遍历