Monday, November 10, 2014

[LeetCode] 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.


思路:

典型的root->leaf path问题,遍历所有path并更新sum。传递的变量是当前节点的path num值curNum。则下一层的节点对应的path num为curNum*10 + val。



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    int sumNumbers(TreeNode *root) {
        int sum = 0;
        sumRootToLeafNum(root, 0, sum);
        return sum;
    }
    
    void sumRootToLeafNum(TreeNode *root, int curNum, int &sum) {
        if(!root) return;
        curNum = curNum*10 + root->val;
        if(!root->left && !root->right) sum += curNum;
        if(root->left) sumRootToLeafNum(root->left, curNum, sum);
        if(root->right) sumRootToLeafNum(root->right, curNum, sum);
    }
};

总结:

当root->leaf path很长时,path num将会很大,sum的时候很容易出现溢出。需要和面试官讨论是否要特殊处理这样的情况。另外当root为NULL时需要返回0.

No comments:

Post a Comment