DAY22 Sum Root to Leaf Numbers

第 11 屆 iThome 鐵人賽

DAY 22

自我挑戰組

刷題記錄與人生分享系列第 22 篇

11th鐵人賽 leetcode c javascript

keyhouse12

2019-09-23 09:04:05

991 瀏覽

分享至

題目:

https://leetcode.com/problems/sum-root-to-leaf-numbers/
一個包含0~9的二元樹，找到其根節點到葉數。

解題思路:

利用遞迴尋訪概念，探訪到每一個節點時乘以10加上現在節點數值，直到條件不符合時。

C版本:

int sumNumbers(struct TreeNode* root) {
    return helper(root, 0);
}

int helper(struct TreeNode* root, int sum)
{
    if(root == NULL)
        return 0;
    if(root -> left == NULL && root -> right == NULL)
        return sum*10 + root -> val;
    return helper(root -> left,sum*10+root -> val) + helper(root -> right,sum*10+root -> val);
}

Javascript版本:

var sumNumbers = function(root) {
    let total = 0, sum = 0;
    helper(root, sum);
    return total;
    
    function helper(node, sum) {
        if (!node) 
return;
        sum = sum*10 + node.val;
        
        if (!node.left && !node.right) {
            total += sum;
        }
        helper(node.left, sum);
        helper(node.right, sum);
    }
};