二叉树遍历与基础操作

二叉树的定义

二叉树是每个节点最多有两个子节点（左子节点和右子节点）的树形结构。

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}

         1          ← 根节点
        / \
       2   3        ← 第 2 层
      / \   \
     4   5   6      ← 第 3 层（叶节点）

常用术语：

• 根节点：没有父节点的节点（树的顶端）
• 叶节点：没有子节点的节点
• 高度：从根到最深叶节点的边数（或节点数，定义略有不同）
• 深度：从根到该节点的边数

三种深度优先遍历（DFS）

二叉树的 DFS 遍历有三种顺序，区别在于何时访问根节点：

递归实现（最简洁）

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

// 中序遍历：左 → 根 → 右
void inorder(TreeNode root, List<Integer> result) {
    if (root == null) return;
    inorder(root.left, result);
    result.add(root.val);        // 中间处理根
    inorder(root.right, result);
}

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

递归的本质：函数调用栈模拟了树的遍历过程，每次调用对应一次入栈，return 对应出栈。

迭代实现（前序，用显式栈）

List<Integer> preorderIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.add(node.val);           // 访问节点
        if (node.right != null) stack.push(node.right);  // 右先入栈（后出）
        if (node.left != null) stack.push(node.left);    // 左后入栈（先出）
    }
    return result;
}

中序迭代（最重要，BST 题目必用）

List<Integer> inorderIterative(TreeNode root) {
    List<Integer> result = 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();
        result.add(cur.val);
        // 转向右子树
        cur = cur.right;
    }
    return result;
}

层序遍历（BFS）

层序遍历按层访问节点，用队列实现。

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;
}

树：        1
           / \
          2   3
         / \
        4   5

层序结果：[[1], [2, 3], [4, 5]]

树的高度与深度

// 二叉树的最大深度（高度）
// 时间 O(n)，空间 O(h)，h 是树高
int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

// 最小深度（到最近叶节点）
int minDepth(TreeNode root) {
    if (root == null) return 0;
    if (root.left == null && root.right == null) return 1;  // 叶节点
    if (root.left == null) return 1 + minDepth(root.right);  // 只有右子树
    if (root.right == null) return 1 + minDepth(root.left); // 只有左子树
    return 1 + Math.min(minDepth(root.left), minDepth(root.right));
}

二叉搜索树（BST）

BST 是有序的二叉树，满足：左子树所有节点 < 根节点 < 右子树所有节点（对每个节点都成立）。

BST 的中序遍历结果是升序序列，这是 BST 最重要的性质。

// BST 搜索（利用有序性，O(h) 时间，平衡时 O(log n)）
TreeNode search(TreeNode root, int target) {
    if (root == null || root.val == target) return root;
    if (target < root.val) return search(root.left, target);
    return search(root.right, target);
}

// BST 验证：中序遍历，检查是否严格递增
boolean isValidBST(TreeNode root) {
    long prev = Long.MIN_VALUE;  // 用 long 防止 int 边界问题
    // 中序迭代的方式实现
    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();
        if (cur.val <= prev) return false;  // 中序值必须严格递增
        prev = cur.val;
        cur = cur.right;
    }
    return true;
}

路径与子树问题

路径总和

// 判断是否存在根到叶的路径，路径和等于 target
boolean hasPathSum(TreeNode root, int target) {
    if (root == null) return false;
    if (root.left == null && root.right == null) return root.val == target;  // 叶节点
    return hasPathSum(root.left, target - root.val)
        || hasPathSum(root.right, target - root.val);
}

对称二叉树

boolean isSymmetric(TreeNode root) {
    return isMirror(root.left, root.right);
}

boolean isMirror(TreeNode l, TreeNode r) {
    if (l == null && r == null) return true;
    if (l == null || r == null) return false;
    return l.val == r.val
        && isMirror(l.left, r.right)  // 外侧对称
        && isMirror(l.right, r.left); // 内侧对称
}

递归思维模式

解树的问题，思考方式是：我（当前节点）要做什么？需要递归告诉我什么？我能给出什么？

大多数树的题目可以归结为两种框架：

框架一：遍历（不需要返回值）

void traverse(TreeNode root) {
    if (root == null) return;
    // 前序位置：处理根节点（可以用全局变量记录结果）
    traverse(root.left);
    // 中序位置
    traverse(root.right);
    // 后序位置：可以获取左右子树的信息
}

框架二：分解（依赖返回值）

int solve(TreeNode root) {
    if (root == null) return 0;             // 基础场景
    int left = solve(root.left);            // 获取左子树的答案
    int right = solve(root.right);          // 获取右子树的答案
    return root.val + Math.max(left, right); // 用左右子树的答案计算当前节点的答案
}

小结

树题解题口诀：

1. 先想清楚：这道题要遍历还是分解？
2. 确定递归的返回值：让子树告诉我什么？
3. 确定基础场景：root 为 null 时返回什么？
4. 写清楚根节点的逻辑：用左右子树的结果怎么计算当前结果？