算法面试——二叉树:遍历、深度、路径问题
·
二叉树是算法面试的"常青树",递归 + 遍历 + 路径类问题是绝对重点。这篇把模板和经典题整理全。
一、前中后序遍历(递归模板)
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
// 前序:根 → 左 → 右
public void preorder(TreeNode root, List<Integer> res) {
if (root == null) return;
res.add(root.val);
preorder(root.left, res);
preorder(root.right, res);
}
// 中序:左 → 根 → 右(二叉搜索树中序有序)
public void inorder(TreeNode root, List<Integer> res) {
if (root == null) return;
inorder(root.left, res);
res.add(root.val);
inorder(root.right, res);
}
// 后序:左 → 右 → 根
public void postorder(TreeNode root, List<Integer> res) {
if (root == null) return;
postorder(root.left, res);
postorder(root.right, res);
res.add(root.val);
}
递归三要素:终止条件、递推关系、返回值。 终止条件永远是 root == null。
二、层序遍历(BFS 队列模板)
// LeetCode 102 二叉树层序遍历
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size(); // 记录当前层节点数
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
result.add(level);
}
return result;
}
关键点:size 必须在循环前记录,否则队列会混入下一层节点。
三、最大深度
// LeetCode 104
public int maxDepth(TreeNode root) {
if (root == null) return 0;
int left = maxDepth(root.left);
int right = maxDepth(root.right);
return Math.max(left, right) + 1;
}
递归自底向上:先算左右子树深度,再加自己一层。
四、路径总和
// LeetCode 112:是否存在 根到叶子 的和等于 target 的路径
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) return false;
// 到叶子节点判断是否等于目标值
if (root.left == null && root.right == null) {
return root.val == targetSum;
}
return hasPathSum(root.left, targetSum - root.val)
|| hasPathSum(root.right, targetSum - root.val);
}
技巧:每层把 target 减去当前节点值,到叶子只需判断一次相等。
五、二叉树进阶模板
// 判断是否对称(LeetCode 101)
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
return isMirror(root.left, root.right);
}
private boolean isMirror(TreeNode a, TreeNode b) {
if (a == null && b == null) return true;
if (a == null || b == null) return false;
return a.val == b.val
&& isMirror(a.left, b.right) // 左对右
&& isMirror(a.right, b.left); // 右对左
}
// 最近公共祖先(LeetCode 236)
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) return root; // 一边一个 → 当前是祖先
return left != null ? left : right;
}
总结
二叉树题永远先想递归:终止条件 + 返回值 + 左右子树合并逻辑。遍历用模板,深度用递归,路径题用"目标值递减"思想。BFS 层序记住 size 先记录。刷熟这几个模板,二叉树面试题 80% 都能直接套。
💡 觉得有用的话,点赞 + 关注【张老师技术栈】吧!
更多推荐


所有评论(0)