[OJ.leetcode] sum-root-to-leaf-numbers

https://oj.leetcode.com/problems/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.

/**

 * Definition for binary tree

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

 

 /*

 1,2,3 = 12+23 = 35.

 

 test case

 [1]

 [1,2]

 [1,2,3,#,#,4,5]

 

 DFS로 접근

1. root에서부터 계속 값을 vector<int> 인자로 넘겨주기.

2. leaf node에서 계속 넘겨받은 인자를 다 더해서 리턴. 

3. 중간 노드에서 리턴으로 넘겨받은 인자를 더해서 리턴.

헷갈린부분 : for (int i=0; i< vector.size() ; i++) {

                //vector.pop_back()을 하면 vector.size()가 계속 변하기 때문에 loop가 생각대로 돌지 않는다. 버그 자주 내는 부분임.

            }

*/

 

 

class Solution {

    public:

    int sumNumbers(TreeNode *root) {

        if(!root) return 0;

        

        vector<int> sum;

        sum.push_back(root->val);

        

        if(!root->left && !root->right) return root->val;

        

        return sumNumbers(root->left, sum) + sumNumbers(root->right, sum);

    }

    

    int sumNumbers(TreeNode* node, vector<int> sum) {

        if(!node) return 0;

        

        sum.push_back(node->val);

        

        if(!node->left && !node->right) { //leaf node

            int temp=0;

            for(int i= sum.size()-1; i >= 0 ; i--) temp += sum[i] * pow(10, (sum.size()-1)-i);

            

            return temp;

        }

        

        return sumNumbers(node->left, sum) + sumNumbers(node->right, sum);

    }

    

};