LeetCode-129

题目

结果

代码

费时费力的算法

class Solution {
    // 全局变量，存储每条路径上从根节点到叶子结点的数字
    private final List<List<Integer>> ans = new LinkedList<>();

    public int sumNumbers(TreeNode root) {
        dfs(root, new LinkedList<>());
        List<Integer> nums = new LinkedList<>();
        ans.forEach(path -> nums.add(parse(path)));
        // 求和并返回
        return nums.stream().reduce(0, Integer::sum);
    }

    // 拼接字符再parse
    private Integer parse(List<Integer> path) {
        StringBuilder s = new StringBuilder();
        for (int num : path) {
            s.append(num);
        }
        return Integer.parseInt(s.toString());
    }

    // 深度优先遍历，途中将数字记录在path里，如果到了叶子结点，将path加到全局变量ans里
    private void dfs(TreeNode root, List<Integer> path) {
        if (root == null) {
            return;
        }
        List<Integer> _path = new LinkedList<>(path);
        _path.add(root.val);
        if (root.left == null && root.right == null) {
            ans.add(new LinkedList<>(_path));
        }
        dfs(root.left, _path);
        dfs(root.right, _path);
    }
}

上面的代码基本思路是，先遍历二叉树得到数字，再求和。

如果可以遍历和求和同时进行，事半功倍。

ez way

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

    private int dfs(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        sum = sum * 10 + root.val;
        if (root.left == null && root.right == null) {
            return sum;
        }
        return dfs(root.left, sum) + dfs(root.right, sum);
    }
}

复杂度

时间复杂度：O（n），遍历

空间复杂度：O（n），栈