Sum Root to Leaf Numbers

LeetCode #129


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.

Example:

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.

    1
   / 
  2  
Return the sum = 12

Idea:

  1. 对于一个node,可能一边有child,另一边为null,需要处理这种情况。所以遇到root==null返回0.
  2. 如果知道一个node是leaf,正常返回。
  3. 返回左边和右边的和,现在的sum值每往下传一层就要x10.

Code:

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        return sumNumbers(root, 0);
    }

    int sumNumbers(TreeNode *root, int sum){
        if(root==NULL) return 0;

        if(root->left==NULL && root->right==NULL) return root->val+sum*10;

        return sumNumbers(root->left, sum*10+root->val)+sumNumbers(root->right, sum*10+root->val);
    }
};

results matching ""

    No results matching ""