LeetCode 112. Path Sum

題目

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example: Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

翻譯

給一個二元樹與另外一個數字sum，判斷二元樹從根加到葉是否有一個路徑可以得到一個與sum相同的數字。

範例：
例如上面的樹，sum = 22，可以找到 5 + 4 + 11 + 2 = 22，因此return true。

思路

1. 使用遞迴來加總每一條路徑的總和，其實就是LeetCode 104. Maximum Depth of Binary Tree的變形，在104中計算的每條路徑的深度，這邊改成計算每個條路徑的總和
2. 以上面範例的樹為例，一開始root[5]，總和s = 0，先計算左節點[4]，這時候s=9
3. [4]沒有右節點，因此只要繼續計算左節點[11]，s = 9 + 11 =20
4. [11]左邊為[7]，s = 27 ， 因為[7]已經是left，所以比對 s == sum ， 不相等就計算下一條路徑
5. [5,4,11,7]這個路徑不符合，退回[5,4,11]，計算[11]的右節點[2]，s = 22，等於sum，因此return true。

解題

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {boolean}
 */
var hasPathSum = function(root, sum) {
    if(root == null) return false;

    // 如果不太清楚怎麼運作，這邊用一個list來儲存每一條root計算後的加總
    // 接開下面三行程式與function sumR2L() 裡面 list.push(s)這行單純是為了看清楚每一條root -> leaf的加總，移除掉不會影響程式執行
    // 測試資料填 [5,4,8,11,null,13,4], 1 ，可以看到加總為[20,16,17] 
    var list = [];
    sumR2L(root,0);
    console.log(list)

    // 起點為root，這時候總和s=0
    return sumR2L(root,0);

    // 遞迴function，計算到目前節點的總和，到leaf的時候停下並且判斷是否與傳入的sum相等
    function sumR2L(root,s){
        // 到底的時候，判斷總和是否與sum相同 
        if(root.left == null && root.right == null){
            list.push(s);   //將root -> leaft 的加總放到list，測試用

            s += root.val;
            return s == sum;
        } 

        // 左邊還沒到底，右邊已經到底，繼續計算左樹的總和
        if(root.left != null && root.right == null){
            return sumR2L(root.left, s+root.val);
        }
         // 右邊還沒到底，左邊已經到底，繼續計算右邊的總和       
        if(root.right != null && root.left == null){
            return sumR2L(root.right, s+root.val);
        }

        // 兩邊的樹都還沒到底，繼續分別計算總和，因為只要有一條路徑成立就是true，因此使用 or來判斷
        return sumR2L(root.left, s+root.val)||sumR2L(root.right, s+root.val);
    }
};