二叉树遍历与高频面试题有哪些？

# 前序遍历：根 → 左 → 右 def preorder(root): if not root: return print(root.val) # 根 preorder(root.left) # 左 preorder(root.right) # 右 # 中序遍历：左 → 根 → 右（BST 得到有序序列） def inorder(root): if not root: return inorder(root.left) print(root.val) inorder(root.right) # 后序遍历：左 → 右 → 根（自底向上） def postorder(root): if not root: return postorder(root.left) postorder(root.right) print(root.val)

from collections import deque def level_order(root): if not root: return [] result = [] queue = deque([root]) while queue: level = [] for _ in range(len(queue)): # 当前层节点数 node = queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(level) return result

# 前序迭代（根左右 → 栈：右左） def preorder_iter(root): if not root: return [] result, stack = [], [root] 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 # 中序迭代（一路向左，再处理） def inorder_iter(root): result, stack = [], [] curr = root while curr or stack: while curr: # 一路向左 stack.append(curr) curr = curr.left curr = stack.pop() result.append(curr.val) curr = curr.right return result # 后序迭代（前序的逆序：根右左 → 反转 → 左右根） def postorder_iter(root): if not root: return [] result, stack = [], [root] 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] # 反转

# 后序递归（自底向上） def max_depth(root): if not root: return 0 left = max_depth(root.left) right = max_depth(root.right) return max(left, right) + 1 # BFS 层序 def max_depth_bfs(root): if not root: return 0 depth = 0 queue = deque([root]) while queue: depth += 1 for _ in range(len(queue)): node = queue.popleft() if node.left: queue.append(node.left) if node.right: queue.append(node.right) return depth

def lowest_common_ancestor(root, p, q): if not root or root == p or root == q: return root left = lowest_common_ancestor(root.left, p, q) right = lowest_common_ancestor(root.right, p, q) # 左右各找到一个 → 当前节点是 LCA if left and right: return root # 只在一边找到 → 返回那一边 return left or right # 原理：后序遍历，自底向上 # 如果 p 和 q 分别在左右子树 → root 是 LCA # 如果 p 和 q 都在左子树 → 返回左子树的 LCA # 如果 p 和 q 都在右子树 → 返回右子树的 LCA

def is_symmetric(root): if not root: return True return check(root.left, root.right) def check(left, right): if not left and not right: return True if not left or not right: return False return (left.val == right.val and check(left.left, right.right) and # 外侧 check(left.right, right.left)) # 内侧

# 是否存在路径和等于 target def has_path_sum(root, target): if not root: return False if not root.left and not root.right: return root.val == target return (has_path_sum(root.left, target - root.val) or has_path_sum(root.right, target - root.val)) # 找出所有路径（回溯） def path_sum(root, target): result = [] def backtrack(node, target, path): if not node: return path.append(node.val) if not node.left and not node.right and node.val == target: result.append(path[:]) backtrack(node.left, target - node.val, path) backtrack(node.right, target - node.val, path) path.pop() # 回溯 backtrack(root, target, []) return result

# 方法1：中序遍历（BST 中序有序） def is_valid_bst(root): prev = float('-inf') def inorder(node): nonlocal prev if not node: return True if not inorder(node.left): return False if node.val <= prev: return False prev = node.val return inorder(node.right) return inorder(root) # 方法2：递归范围判断 def is_valid_bst2(root): def check(node, low, high): if not node: return True if node.val <= low or node.val >= high: return False return (check(node.left, low, node.val) and check(node.right, node.val, high)) return check(root, float('-inf'), float('inf'))