leetcode Question 130: Sum Root to Leaf Numbers

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.

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.

Analysis:

Once we see this kind of problem, no matter what sum is required to output, "all root-to-leaf" phrase reminds us the classic Tree Traversal or Depth-First-Search algorithm. Then according to the specific problem, compute and store the values we need. Here in this problem, while searching deeper, add the values up (times 10 + current value), and add the sum to final result if meet the leaf node (left and right child are both NULL).

Code(C++):

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

    void dfs(TreeNode* root,int cur, int &res){
        if (root->left==NULL && root->right==NULL){
            cur=cur*10+root->val;
            res+=cur;
        }else{
            cur=cur*10+root->val;
            if (root->left){
                dfs(root->left,cur,res);
            }
            if (root->right){
                dfs(root->right,cur,res);
            }
        }
    }
    int sumNumbers(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int res=0;
        if (!root){return res;}
        dfs(root,0,res);
        return res;
    }
};

Code(Python):

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param root, a tree node
    # @return an integer
    res = 0
    def search(self, root, path):
        if root.left == None and root.right == None:
            self.res += path + root.val
        else:
            if root.left != None:
                self.search(root.left, (path + root.val)*10)
            if root.right != None:
                self.search(root.right, (path + root.val)*10)
            
    def sumNumbers(self, root):
        self.res = 0
        if root == None:
            return 0
        else:
            self.search(root, 0)
            return self.res