[LeetCode] Sum Root to Leaf Numbers

 

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.

 

问题描述：给定一个二叉树，它的节点值的范围是[0, 9]，每个从根节点到叶子节点的路径代表一个整数。如图中的例子，求出这个二叉树中所有的从根节点到叶子节点的整数的和。

 

提到二叉树，首先应该想到的是递归方法，如图，左子树的值是2，右子树的值是3，然后sum = 1 * pow(10, depth(lchild)) + 1 * pow(10, depth(lchild)) + sumNumbers(lchild) + sumNumbers(rchild);当叶子节点的深度都一样时，这种方法是很直观而且简单的，但是，如果叶子深度不一样呢？比如

      1

     / \

    2   3

   / \

  4   5  

左子树的值是24 + 25 = 49，右子树的值是3，那么sum是否等于1 * pow(10, depth(lchild)) + 1 * pow(10, depth(rchild)) + sumNumbers(lchild) + sumNumbers(rchild);这里的主要问题是当该节点计算的次数要根据该节点所有的叶子节点来得到。就拿这个例子来说：

sum = 1 * pow(10, depth(leaf(4))) + 1 * pow(10, depth(leaf(5))) + 1 * pow(10, depth(leaf(3))) + sumNumbers(lchild) + sumNumbers(rchild);

 

depth(leaf(4))表示叶子节点4的深度，这里应该是2，因为这里的深度是相对于1来说的。

 

我们的代码里面包含两个函数：

 

（1）vector<int> leafDepth(TreeNode *root, int lev)    返回root节点的所有叶子节点的层次的结合，这个层次是相对于root而言的

 

（2） int sumNumbers(TreeNode *root)    返回root节点的从root到叶子节点的整数的和，它递归遍历整个树。

 

class Solution {  
public:  
    vector<int> leafDepth(TreeNode *root, int lev)  
    {  
        if(root == NULL)  
            return vector<int>();  
  
        if(root->left == NULL && root->right == NULL) {  
            vector<int> vec;  
            vec.push_back(lev);  
            return vec;  
        }  
          
        ++lev;  
  
        if(root->left == NULL && root->right) {  
            return leafDepth(root->right, lev);  
        }  
  
        if(root->left && root->right == NULL) {  
            return leafDepth(root->left, lev);  
        }  
  
        if(root->left && root->right) {  
            vector<int> lvec = leafDepth(root->left, lev);  
            vector<int> rvec = leafDepth(root->right, lev);  
            for(vector<int>::iterator iter = rvec.begin();  
                                      iter != rvec.end(); ++iter) {  
                lvec.push_back(*iter);  
            }  
            return lvec;  
        }  
    }  
      
    int sumNumbers(TreeNode *root)   
    {  
        // IMPORTANT: Please reset any member data you declared, as  
        // the same Solution instance will be reused for each test case.  
        if(root == NULL)  
            return 0;  
          
        if(root->left == NULL && root->right == NULL) {  
            return root->val;  
        }  
          
        int lev = 0;  
        int sum = 0;  
          
        vector<int> vec = leafDepth(root, lev);  
        for(vector<int>::iterator iter = vec.begin();  
                                  iter != vec.end(); ++iter) {  
            sum += (root->val) * pow(10, *iter);  
        }  
          
        if(root->left == NULL && root->right)  
            sum += sumNumbers(root->right);  
        else if(root->left && root->right == NULL)  
            sum += sumNumbers(root->left);  
        else  
            sum += sumNumbers(root->left) + sumNumbers(root->right);  
          
        return sum;  
    }  
};  

 

补充：软件开发 , C++ ,