Leetcode 129 求根到叶子节点数字之和 DFS优化

　　DFS 解法，通过回溯一个 StringBuilder 记录下所有路径代表的数字并求和：

    StringBuilder sb = new StringBuilder();
    int re = 0;

    public int sumNumbers(TreeNode root) {
        if (root == null) {
            return 0;
        }
        getNums(root);
        return re;
    }

    public void getNums(TreeNode root) {
        if (root.right == null && root.left == null) {
            sb.append(root.val);
            Integer num = Integer.valueOf(sb.toString());
            re += num;
            sb.deleteCharAt(sb.length() - 1);
            return;
        }
        sb.append(root.val);
        if (root.left != null) {
            getNums(root.left);
        }
        if (root.right != null) {
            getNums(root.right);
        }
        sb.deleteCharAt(sb.length() - 1);
    }

　　本着上面的思路，进行 DFS 表示的优化。只考虑单个节点可能遇到的情况：

　　1、为叶子节点，直接返回该节点的值

　　2、存在子节点，返回当前节点乘10分别加左右子节点并求和

    public final int sumNumbers0(TreeNode root) {
        return getNums(root, 0);
    }

    public final int getNums(TreeNode root, int preSum) {
        if (root == null) {
            return 0;
        }
        int sum = preSum * 10 + root.val;
        if (root.left == null && root.right == null) {
            return sum;
        }
        return getNums(root.right, sum) + getNums(root.left, sum);
    }