二叉树深度优先搜索：核心原理与实战案例

2. 求根节点到叶节点数字之和

每条从根到叶的路径代表一个数字（例如路径 1->2->3 代表 123），需要计算所有路径数字的总和。

思路： 使用 DFS 传递当前路径累积的和 preSum。每进入一层，将当前节点值加入 preSum（左移一位加当前值）。到达叶子节点时，累加该路径值。注意处理空指针的情况。

class Solution {
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }

    private int dfs(TreeNode root, int preSum) {
        // 更新当前路径数值
        preSum = preSum * 10 + root.val;
        
        // 叶子节点，返回当前累积值
        if (root.left == null && root.right == null) {
            return preSum;
        }

        int ret = 0;
        // 递归左子树
        if (root.left != null) {
            ret += dfs(root.left, preSum);
        }
        // 递归右子树
        if (root.right != null) {
            ret += dfs(root.right, preSum);
        }
        return ret;
    }
}

3. 二叉树剪枝

移除所有不包含 1 的子树。如果一个节点及其子树全为 0，则该节点应被删除。

思路： 必须采用后序遍历。先处理左右子树，判断它们是否应该保留。如果左右子树都被剪掉且当前节点值为 0，则当前节点也应被剪掉（返回 null）。

class Solution {
    public TreeNode pruneTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        // 递归剪枝左右子树
        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);
        
        // 如果左右子树均为空且自身为 0，则剪掉当前节点
        if (root.left == null && root.right == null && root.val == 0) {
            return null;
        }
        return root;
    }
}

4. 验证二叉搜索树

判断一棵树是否为有效的二叉搜索树（BST）。BST 的中序遍历结果应当是严格递增的。

思路： 利用中序遍历的特性。维护一个全局变量 prev 记录前一个访问节点的值。如果当前节点值小于等于 prev，则不是 BST。为了优化性能，一旦发现不合法，立即剪枝返回 false。

class Solution {
    long prev = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        // 递归左子树
        boolean left = isValidBST(root.left);
        if (!left) {
            return false; // 剪枝
        }
        
        // 检查当前节点
        boolean cur = root.val > prev;
        prev = root.val;
        
        // 递归右子树
        boolean right = isValidBST(root.right);
        return left && cur && right;
    }
}

5. 二叉搜索树中第 K 小的元素

在中序遍历中找到第 K 个节点的值。

思路： 同样利用中序遍历的有序性。使用计数器 count，每访问一个节点减一。当 count 为 0 时，当前节点即为目标。找到后立即停止遍历以节省时间。

class Solution {
    int count;
    int ret;

    public int kthSmallest(TreeNode root, int k) {
        count = k;
        inOrder(root);
        return ret;
    }

    public void inOrder(TreeNode root) {
        if (root == null || count == 0) {
            return;
        }
        inOrder(root.left);
        count--;
        if (count == 0) {
            ret = root.val;
            return;
        }
        inOrder(root.right);
    }
}

6. 二叉树的所有路径

找出所有从根到叶子的路径，格式如 "1->2->4"。

思路： 使用前序遍历构建路径字符串。为了避免回溯时手动删除字符的麻烦，可以将路径字符串作为参数传递给下一层递归。每次递归创建一个新的字符串副本，这样就不会影响上一层的状态。遇到叶子节点时将完整路径加入结果列表。

import java.util.ArrayList;
import java.util.List;

class Solution {
    List<String> ret;

    public List<String> binaryTreePaths(TreeNode root) {
        ret = new ArrayList<>();
        if (root == null) return ret;
        dfs(root, new StringBuilder());
        return ret;
    }

    private void dfs(TreeNode root, StringBuilder path) {
        int len = path.length();
        path.append(root.val);
        
        // 叶子节点，保存路径
        if (root.left == null && root.right == null) {
            ret.add(path.toString());
        } else {
            path.append("->");
            if (root.left != null) {
                dfs(root.left, path);
            }
            if (root.right != null) {
                dfs(root.right, path);
            }
        }
        // 回溯：恢复现场，移除当前添加的内容
        while (path.length() > len) {
            path.deleteCharAt(path.length() - 1);
        }
    }
}

以上六个案例涵盖了 DFS 在树形结构中的常见应用场景。掌握递归的入口设计、状态传递以及剪枝优化，是解决此类问题的关键。在实际编码中，注意边界条件（如空树、单节点）的处理，能让代码更加健壮。