题目描述

给定一个二叉树,它的每个结点都存放一个 0-9 的数字,每条从根到叶子节点的路径都代表一个数字。

例如,从根到叶子节点路径 1->2->3 代表数字 123

计算从根到叶子节点生成的所有数字之和。

说明: 叶子节点是指没有子节点的节点。

示例 1:

输入: [1,2,3]
    1
   / \
  2   3
输出: 25
解释:
从根到叶子节点路径 1->2 代表数字 12.
从根到叶子节点路径 1->3 代表数字 13.
因此,数字总和 = 12 + 13 = 25.

示例 2:

输入: [4,9,0,5,1]
    4
   / \
  9   0
 / \
5   1
输出: 1026
解释:
从根到叶子节点路径 4->9->5 代表数字 495.
从根到叶子节点路径 4->9->1 代表数字 491.
从根到叶子节点路径 4->0 代表数字 40.
因此,数字总和 = 495 + 491 + 40 = 1026.

https://leetcode-cn.com/problems/sum-root-to-leaf-numbers/

解法1 – 先序遍历

按照题目的描述,很自然就能够想到使用先序遍历访问二叉树,我们使用变量accu累积从跟节点到当前节点走过的节点构成到数字,其中accu = accu*10 + node.val。当我们走到叶节点时,将accu累加到结果ans[0]中。由于Java不支持引用传参(pass-by-reference),我们使用1个元素的数组来存放结果,当然也可以通过成员变量来实现。

时间复杂度O(n),空间复杂度O(n)(调用栈开销)。全部代码如下:

class Solution {
    public int sumNumbers(TreeNode root) {
        int[] ans = new int[1];

        helper(root, 0, ans);

        return ans[0];
    }

    private void helper(TreeNode node, int accu, int[] ans) {

        if (node == null)
            return;

        accu = accu * 10 + node.val;

        if (node.left == null && node.right == null)
            ans[0] += accu;
        else {
            helper(node.left, accu, ans);
            helper(node.right, accu, ans);
        }

    }
}

解法2 – 层次遍历

这道题也可以采用BFS方法来做。我们设置两个队列,一个是nodeQueue,用于记录当前节点下一层待访问的节点;另一个是accuQueue,用于记录从跟节点到当前节点路径构成的数字,这两个队列是保持同步的。

我们首先将跟节点入队nodeQueue,跟节点的值入队accuQueue,还设置一个ans变量用存放结果。当队列不为空时,我们从nodeQueue取出节点node,从accuQueue取出路径构成的数字accu,如果node是叶子节点,我们就把accu累加到ans;如果node的左子树非空,我们就将node.left入队nodeQueue,将accu*10 + node.left.val入队accuQueue;如果node右子树非空,就将node.right入队nodeQueue,将accu*10+node.right.val入队accuQueue。这样的操作不断地循环下去,直到队列为空,此时ans就已经累积了从跟节点到所有叶节点的数字和。

时间复杂度O(n),空间复杂度O(n),关于空间复杂度的分析参考这个。全部代码如下:

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int sumNumbers(TreeNode root) {
        int ans = 0;
        if (root == null)
            return ans;
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        Queue<Integer> accuQueue = new LinkedList<>();

        nodeQueue.offer(root);
        accuQueue.offer(root.val);

        while (!nodeQueue.isEmpty()) {
            int size = nodeQueue.size();

            while (size-- > 0) {
                TreeNode node = nodeQueue.poll();
                int accu = accuQueue.poll();

                if (node.left == null && node.right == null)
                    ans += accu;
                else {
                    if (node.left != null) {
                        nodeQueue.offer(node.left);
                        accuQueue.offer(accu * 10 + node.left.val);
                    }
                    if (node.right != null) {
                        nodeQueue.offer(node.right);
                        accuQueue.offer(accu * 10 + node.right.val);
                    }
                }
            }
        }

        return ans;
    }
}
pwrliang Algorithms, BFS, DFS, Tree

Leave a Reply

Your email address will not be published. Required fields are marked *