SYSTEM
二叉树
src/content/notes/system/二叉树.md 1.3 二叉树
前中后序遍历(递归 + 迭代)
递归版简洁;迭代版用栈模拟,前序最直观,中序需先把左子树全部压栈,后序可用”根右左”反转或双栈。
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
class Solution {
// 前序递归
public List<Integer> preorder(TreeNode root) {
List<Integer> res = new ArrayList<>();
preorder(root, res);
return res;
}
private void preorder(TreeNode node, List<Integer> res) {
if (node == null) return;
res.add(node.val);
preorder(node.left, res);
preorder(node.right, res);
}
// 中序迭代:先把左子树一路压栈
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
while (cur != null) { stack.push(cur); cur = cur.left; }
cur = stack.pop();
res.add(cur.val);
cur = cur.right;
}
return res;
}
// 后序迭代:根右左 反转 = 左右根
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
if (root == null) return res;
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
res.add(node.val); // 根
if (node.left != null) stack.push(node.left);
if (node.right != null) stack.push(node.right);
}
Collections.reverse(res); // 反转得到 左右根
return res;
}
}
层序遍历(BFS,力扣 102)
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size(); // 一次取一层
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = q.poll();
level.add(node.val);
if (node.left != null) q.offer(node.left);
if (node.right != null) q.offer(node.right);
}
res.add(level);
}
return res;
}
}
最近公共祖先(力扣 236)
后序递归:在左右子树分别找 p、q,若分散在两侧则当前节点就是 LCA。
class Solution {
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; // 一左一右,当前即 LCA
return left != null ? left : right; // 都在一侧
}
}
面试题:“二叉树的非递归遍历怎么写?”
用栈模拟递归的调用栈。前序:访问根→右入栈→左入栈;中序:一路把左子树压栈,弹出时访问并转向右子树;后序:用”根→右→左”的反向先序遍历,结果反转即得后序。关键是利用栈的 LIFO 改变访问顺序。