二叉树 DFS、回溯与几道经典题的写法

3.2 求根节点到叶节点数字之和

这题要求把每条根到叶子的路径当成一个数字，最后把所有数字加起来。路径上的值要一路向下拼接，到了叶子节点再结算。

这里递归参数里带一个 preSum 会比较顺手。每往下一层，就把当前节点接到数字后面；走到叶子时直接返回这个路径值。这样不用额外维护路径字符串，逻辑也更紧凑。代码里那种'先乘 10，再加当前值'的写法，基本就是这类题的标准处理方式。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *   int val;
 *   TreeNode left;
 *   TreeNode right;
 *   TreeNode() {}
 *   TreeNode(int val) { this.val = val; }
 *   TreeNode(int val, TreeNode left, TreeNode right) {
 *     this.val = val; this.left = left; this.right = right;
 *   }
 * }
 */
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.3 二叉树剪枝

题意很直接：删掉所有不包含 1 的子树。也就是说，一个节点如果最后只剩下自己，而且值还是 0，它就没必要留着。

这类题还是得用后序遍历。原因很简单，想知道当前节点能不能删，必须先知道左右子树有没有留下东西。先递归处理左右孩子，再回到当前节点判断是不是'空且为 0'，是的话返回 null。把返回值接回父节点，剪枝就完成了。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *   int val;
 *   TreeNode left;
 *   TreeNode right;
 *   TreeNode() {}
 *   TreeNode(int val) { this.val = val; }
 *   TreeNode(int val, TreeNode left, TreeNode right) {
 *     this.val = val; this.left = left; this.right = right;
 *   }
 * }
 */
class Solution {
    public TreeNode pruneTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);
        if (root.left == null && root.right == null && root.val == 0) {
            return null;
        }
        return root;
    }
}

3.4 验证二叉搜索树

二叉搜索树最顺手的判断方式，就是中序遍历。因为它遍历出来天然是递增序列，只要当前节点值比前一个节点大，整棵树就继续成立；一旦不满足，后面也不用看了。

这里用一个 prev 记录前一个访问到的值会比较省事。递归到当前节点时，先去看左子树，左边不合法就直接返回。然后比较当前值和 prev，更新 prev，最后再递归右子树。题里其实没有什么花活，关键是尽早停，不要傻乎乎把整棵树都扫完。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *   int val;
 *   TreeNode left;
 *   TreeNode right;
 *   TreeNode() {}
 *   TreeNode(int val) { this.val = val; }
 *   TreeNode(int val, TreeNode left, TreeNode right) {
 *     this.val = val; this.left = left; this.right = right;
 *   }
 * }
 */
class Solution {
    long prev = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        boolean left = isValidBST(root.left);
        // 剪枝
        if (left == false) return false;
        boolean cur = false;
        if (root.val > prev) cur = true;
        prev = root.val;
        boolean right = isValidBST(root.right);
        return left && cur && right;
    }
}

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

这题和上一题很像，还是靠中序遍历。不同的是，这里要找的是第 k 个节点，所以再加一个计数器就够了。

遍历到一个节点就让 count--，当 count == 0 时，当前节点就是答案，直接记录下来并停止继续搜索。这个地方的剪枝很有用，没必要把后面的节点也走完。代码里保留两个全局变量，一个记数，一个存结果，思路清楚，写起来也干净。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *   int val;
 *   TreeNode left;
 *   TreeNode right;
 *   TreeNode() {}
 *   TreeNode(int val) { this.val = val; }
 *   TreeNode(int val, TreeNode left, TreeNode right) {
 *     this.val = val; this.left = left; this.right = right;
 *   }
 * }
 */
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;
        if (count == 0) return;
        InOrder(root.right);
    }
}

3.6 二叉树的所有路径

这题要输出所有从根到叶子的路径，格式是字符串，中间用 -> 连起来。

写回溯时，路径字符串最容易出问题的地方就是'恢复现场'。你如果把同一个字符串对象一路往下改，回来的时候就很容易串掉。所以我更倾向于把当前路径作为参数传下去，每一层自己拷贝一份，再追加当前节点值。叶子节点直接把路径放进结果集，不是叶子就补上 -> 再继续往下走。处理到左子树为空、右子树不为空的情况时，正常继续递归就行，没必要额外绕一层判断。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *   int val;
 *   TreeNode left;
 *   TreeNode right;
 *   TreeNode() {}
 *   TreeNode(int val) { this.val = val; }
 *   TreeNode(int val, TreeNode left, TreeNode right) {
 *     this.val = val; this.left = left; this.right = right;
 *   }
 * }
 */
class Solution {
    List<String> ret;

    public List<String> binaryTreePaths(TreeNode root) {
        ret = new ArrayList<>();
        DFS(root, new StringBuffer());
        return ret;
    }

    public void DFS(TreeNode root, StringBuffer _path) {
        StringBuffer path = new StringBuffer(_path);
        path.append(Integer.toString(root.val));
        if (root.left == null && root.right == null) {
            ret.add(path.toString());
            return;
        }
        path.append("->");
        if (root.left != null) DFS(root.left, path);
        if (root.right != null) DFS(root.right, path);
    }
}