SumROotToLeafNumbers [source code]

public class SumROotToLeafNumbers {
static
/******************************************************************************/
class Solution {
    public int sumNumbers(TreeNode root) {
        if (root == null)
            return 0;
        Paths res = new Paths (0, 0);
        dfs (root, res);
        return res.sum;
    }

    void dfs (TreeNode node, Paths ps) {
        ps.path = ps.path * 10 + node.val;
        if (node.left == null && node.right == null) {
            ps.sum += ps.path;
        } else {
            if (node.left != null)
                dfs (node.left, ps);
            if (node.right != null)
                dfs (node.right, ps);
        }
        ps.path /= 10;
    }

    static class Paths {
        int path, sum;
        Paths (int p, int ps) {this.path = p; this.sum = ps; }
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        SumROotToLeafNumbers.Solution tester = new SumROotToLeafNumbers.Solution();
    }
}

这题首先一个特点就是, 给的例子不够typical, 所以这题上来的一个事情就是先自己举一个例子;

本来还想说跟depth有什么关系, 后来想想, 实际上走一遍DFS就行了, 在leaf的位置collect;

这题好像用returned recursion不如用mutation recursion, 因为比如这个图:

2和3返回上来两个sum, 但是单凭这两个sum, 1还不知道自己当前root level decision应该干什么; 因为1还必须知道左右两个subtree的leaf的数量; 这样就让这个return的过程很复杂; 不如直接用path mutation的方法来在最后leaf的位置收集就行了;

既然用这个思路, 另外一个问题也就出来了, 这题是用leaf位置判断还是pre leaf位置判断?

最后还是比较快的AC了, 速度是1ms (24%), 有过几个小bug;

没有editorial;

https://leetcode.com/problems/sum-root-to-leaf-numbers/discuss/41363/Short-Java-solution.-Recursion.

I use recursive solution to solve the problem.

public int sumNumbers(TreeNode root) {  
    return sum(root, 0);  
}  

public int sum(TreeNode n, int s){  
    if (n == null) return 0;  
    if (n.right == null && n.left == null) return s*10 + n.val;  
    return sum(n.left, s*10 + n.val) + sum(n.right, s*10 + n.val);  
}

好像returned recursion也没有很复杂的样子;

底下很多人都想到了这个做法, 好像这题的关键就是一个pre Null位置的判断;

The return type provided by problem creator is ‘int’. So I think we shouldn’t consider overflow.

https://leetcode.com/problems/sum-root-to-leaf-numbers/discuss/41400/Can-you-improve-this-algorithm

I prefer the iterative method over recursion. I used 2 queues to do a breadth first traversal. both time and space complexity is O(N):

public class Solution {  
    public int sumNumbers(TreeNode root) {  
        int total = 0;  
        LinkedList<TreeNode> q = new LinkedList<TreeNode>();  
        LinkedList<Integer> sumq = new LinkedList<Integer>();  
        if(root !=null){  
            q.addLast(root);  
            sumq.addLast(root.val);  
        }  
        while(!q.isEmpty()){  
            TreeNode current = q.removeFirst();  
            int partialSum = sumq.removeFirst();  
            if(current.left == null && current.right==null){  
                total+=partialSum;  
            }else{  
                if(current.right !=null){  
                    q.addLast(current.right);  
                    sumq.addLast(partialSum*10+current.right.val);  
                }  
                if(current.left !=null){  
                    q.addLast(current.left);  
                    sumq.addLast(partialSum*10+current.left.val);  
                }  

            }  

        }  
        return total;  
    }  
}

看起来很slick, 实际上代码写的很一般; 并行queue的做法以前是见过的; 因为我们的node本身是一个tree都在被一个queue记录, 所以每一个queue对应的这个path, which also forms a tree, 也需要一个单独的queue来记录;

We can do it without helper function.

class Solution:  
# @param root, a tree node  
# @return an integer  
def sumNumbers(self, root):  
    if not root:  
        return 0  
    if not root.left and not root.right:  
        return root.val  
    val = 0  
    if root.left:  
        root.left.val += root.val * 10  
        val += self.sumNumbers(root.left)  
        root.left.val -= root.val * 10  
    if root.right:  
        root.right.val += root.val * 10  
        val += self.sumNumbers(root.right)  
        root.right.val -= root.val * 10  
    return val

这个就比较的hackish了, 看看还是可以的; 实际上就是一个理解DFS本身的顺序, 直接在向下recurse的时候, 把整个path都直接扔到下一个child的val上面;

int sumNumbers(TreeNode *root) {  
    int sum = 0;  
    if(root == NULL) return sum;  
    stack<TreeNode *> array;  
    stack<int> val;  
    array.push(root);  
    val.push(0);  
    while(!array.empty()){  
        TreeNode *node = array.top();  
        int prev = val.top();  
        array.pop();  
        val.pop();  
        while(node->left != NULL){  
            int cur = prev*10 + node->val;  
            if(node->right != NULL){  
                array.push(node->right);  
                val.push(cur);  
            }  
            prev = cur;  
            node = node->left;  
        }  
        int cur = prev*10 + node->val;  
        if(node->right == NULL){  
            sum += cur;  
        }else{  
            array.push(node->right);  
            val.push(cur);  
        }  
    }  
    return sum;  
}

submission最优解基本就是上面这个做法了;

Problem Description

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.

For example,

    1  
   / \  
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

Difficulty:Medium
Total Accepted:130.7K
Total Submissions:347.8K
Contributor:LeetCode
Related Topics
treedepth-first search
Similar Questions
Path SumBinary Tree Maximum Path Sum