Leetcode日记--129. Sum Root to Leaf Numbers

题目如下:

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

Note: A leaf is a node with no children.

Example1:

Input: [1,2,3]
1
/ \
2 3
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.

Example 2:

Input: [4,9,0,5,1]
4
/ \
9 0
 / \
5 1
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.

思路

方法一:递归,深度优先

这个思路很容易想到,就是上一层的值往下传并乘以10,加上本层的值,每次递归,直到加到最底下一层。

代码如下:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int sumNumbers(TreeNode root) {
        // if(root==null)
            // return 0;
        return helper(root,0);
    }
    public int helper(TreeNode root,int lastLayerVal){
        if(root==null)
            return 0;
        // int leftSum=0,rightSum=0;
        int thisLayerVal = lastLayerVal*10 + root.val;
        if(root.left!=null||root.right!=null)
            return helper(root.left,thisLayerVal) + helper(root.right,thisLayerVal);
        else
            return thisLayerVal;
    }
}

方法二:广度优先,迭代

使用广度优先搜索,需要维护两个队列,分别存储节点和节点对应的数字。

初始时,将根节点和根节点的值分别加入两个队列。每次从两个队列分别取出一个节点和一个数字,进行如下操作:

如果当前节点是叶子节点,则将该节点对应的数字加到数字之和;

如果当前节点不是叶子节点,则获得当前节点的非空子节点,并根据当前节点对应的数字和子节点的值计算子节点对应的数字,然后将子节点和子节点对应的数字分别加入两个队列。

搜索结束后,即可得到所有叶子节点对应的数字之和。

class Solution {
    public int sumNumbers(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int sum = 0;
        Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
        Queue<Integer> numQueue = new LinkedList<Integer>();
        nodeQueue.offer(root);
        numQueue.offer(root.val);
        while (!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.poll();
            int num = numQueue.poll();
            TreeNode left = node.left, right = node.right;
            if (left == null && right == null) {
                sum += num;
            } else {
                if (left != null) {
                    nodeQueue.offer(left);
                    numQueue.offer(num * 10 + left.val);
                }
                if (right != null) {
                    nodeQueue.offer(right);
                    numQueue.offer(num * 10 + right.val);
                }
            }
        }
        return sum;
    }
}

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/sum-root-to-leaf-numbers/solution/qiu-gen-dao-xie-zi-jie-dian-shu-zi-zhi-he-by-leetc/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注