← 返回学习路线

SYSTEM

二叉树

八股1.3 二叉树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 改变访问顺序。