129. Sum Root to Leaf Numbers

https://leetcode.com/problems/sum-root-to-leaf-numbers

Sum Root to Leaf Numbers - LeetCode

 

이진트리의 root가 주어졌을 때, root부터 leaf까지 발생하는 unique한 path들의 val을 각 자리수로 대입해 한 정수로 만들고, 모든 정수의 합을 반환하는 문제다.

 

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void solve(TreeNode* node, int num) {
        if (!node) {
            return;
        }
        
        num = num * 10 + node->val;
        
        if (!node->left && !node->right)
        {
            sum_ += num;
            return;
        }
        
        solve(node->left, num);
        solve(node->right, num);
    }
    
    int sumNumbers(TreeNode* root) {
        sum_ = 0;
        solve(root, 0);
        return sum_;
    }

private:
    int sum_;
};