二叉树遍历（递归与迭代，BFS层序）

三种递归遍历

class TreeNode { int val; TreeNode left, right; }

// 前序：根 → 左 → 右
void preorder(TreeNode root, List<Integer> res) {
    if (root == null) return;
    res.add(root.val);
    preorder(root.left, res);
    preorder(root.right, res);
}

// 中序：左 → 根 → 右（BST 中序 = 有序序列）
void inorder(TreeNode root, List<Integer> res) {
    if (root == null) return;
    inorder(root.left, res);
    res.add(root.val);
    inorder(root.right, res);
}

// 后序：左 → 右 → 根
void postorder(TreeNode root, List<Integer> res) {
    if (root == null) return;
    postorder(root.left, res);
    postorder(root.right, res);
    res.add(root.val);
}

迭代遍历（生产高频）

前序迭代

List<Integer> preorderIterative(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    if (root != null) stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        res.add(node.val);
        if (node.right != null) stack.push(node.right);  // 先入右，后出
        if (node.left != null) stack.push(node.left);
    }
    return res;
}

中序迭代

List<Integer> inorderIterative(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;
}

后序迭代

List<Integer> postorderIterative(TreeNode root) {
    LinkedList<Integer> res = new LinkedList<>();  // 用 LinkedList 方便头插
    Deque<TreeNode> stack = new ArrayDeque<>();
    if (root != null) stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        res.addFirst(node.val);  // 头插
        if (node.left != null) stack.push(node.left);
        if (node.right != null) stack.push(node.right);
    }
    return res;
}

层序遍历（BFS，LeetCode 102）

List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    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);
        }
        res.add(level);
    }
    return res;
}

BFS 变种

// 锯齿形（LeetCode 103）：奇偶层交替方向
if (level % 2 == 0) level.add(node.val);
else level.addFirst(node.val);  // LinkedList 头插

// 最大宽度（LeetCode 662）：BFS 时记录节点编号（父节点 i → 子节点 2i, 2i+1）

二叉树属性

// 最大深度
int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

// 是否平衡（左右子树高度差 ≤ 1）
int checkHeight(TreeNode root) {
    if (root == null) return 0;
    int left = checkHeight(root.left);
    if (left == -1) return -1;
    int right = checkHeight(root.right);
    if (right == -1) return -1;
    return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right);
}
boolean isBalanced(TreeNode root) { return checkHeight(root) != -1; }

// 是否对称（LeetCode 101）
boolean isSymmetric(TreeNode root) { return mirror(root.left, root.right); }
boolean mirror(TreeNode a, TreeNode b) {
    if (a == null && b == null) return true;
    if (a == null || b == null) return false;
    return a.val == b.val && mirror(a.left, b.right) && mirror(a.right, b.left);
}