力扣 - 129. 求根到叶子节点数字之和

题目

129. 求根到叶子节点数字之和

思路1（DFS 深度优先搜索）

• 通过深度优先搜索，自顶向下
• 参数列表加了一个preSum参数，用于存储上父节点的数的大小
• 将preSum与本结点的val进行计算，得到一个结果，次结果作为下一个结点的父节点preSum参数，传递进去
• 如果遍历到空，就返回0
• 否则返回的值就是两个孩子的val相加

代码

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

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

复杂度分析

• 时间复杂度：\(O(N)\)，其中 N 为结点数
• 空间复杂度：\(O(N)\)，其中 N 为结点数

思路2（BFS 广度优先搜索）

• 通过广度优先搜索
• 利用两个队列来实现，一个队列存储树的结点，另一个存储累计的值
• 遍历到末尾才将结果加入sum中

代码

class Solution {
    public int sumNumbers(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        Deque<TreeNode> q1 = new LinkedList<>();
        Deque<Integer> q2 = new LinkedList<>();
        q1.offer(root);
        q2.offer(root.val);
        // 用来计算总和
        int sum = 0;

        while (!q1.isEmpty()) {
            TreeNode node = q1.poll();
            int num = q2.poll();
            
            // 只有到达根节点才计算
            if (node.left == null && node.right == null) {
                sum += num;
            } else {
                // 否则的话讲当前的值计算一下带入到下一步运算中
                if (node.left != null) {
                    q1.offer(node.left);
                    q2.offer(num * 10 + node.left.val);
                }
                if (node.right != null) {
                    q1.offer(node.right);
                    q2.offer(num * 10 + node.right.val);
                }
            }
        }
        return sum;
    }
}

复杂度分析

• 时间复杂度：\(O(N)\)，其中 N 为结点数
• 空间复杂度：\(O(N)\)，其中 N 为结点数