112. 路徑總和

題目連結：112. 路徑總和(簡單)

給你二叉樹的根節點

root

和一個表示目标和的整數

targetSum

。判斷該樹中是否存在 根節點到葉子節點 的路徑，這條路徑上所有節點值相加等于目标和

targetSum

。如果存在，傳回

true

；否則，傳回

false

。

葉子節點 是指沒有子節點的節點。

示例 1：

輸入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
輸出：true
解釋：等于目标和的根節點到葉節點路徑如上圖所示。      

示例 2：

輸入：root = [1,2,3], targetSum = 5
輸出：false
解釋：樹中存在兩條根節點到葉子節點的路徑：
(1 --> 2): 和為 3
(1 --> 3): 和為 4
不存在 sum = 5 的根節點到葉子節點的路徑。      

示例 3：

輸入：root = [], targetSum = 0
輸出：false
解釋：由于樹是空的，是以不存在根節點到葉子節點的路徑。      

解題思路

該題與257. 二叉樹的所有路徑 很相似，隻是在該題中，如果找到對應的路徑需立即傳回。是以在遞歸方法中，遞歸函數的傳回值不能為 void。

遞歸法

代碼(C++)

//遞歸
class Solution {
public:
     bool traversal(TreeNode* node, int targetSum, int& midSum) {
        if (node->left == nullptr && node->right == nullptr) { // 葉子節點
            if (midSum == targetSum) return true;
            else return false;
        }
        //非葉子節點
        bool result1 = false;
        bool result2 = false;
        if (node->left) {
            midSum += node->left->val;
            result1 = traversal(node->left, targetSum, midSum);
            midSum -= node->left->val; //回溯
        }
        if (node->right) {
            midSum += node->right->val;
            result2 = traversal(node->right, targetSum, midSum);
            midSum -= node->right->val; //回溯
        }
        return result1 || result2;
    }
​
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (root == nullptr) return false;
        int midSum = root->val;
        bool result = traversal(root, targetSum, midSum);
        return result;
    }
};      

代碼(JavaScript)

// 遞歸法
// 用 count 計數 
function traversal(node, count) {
    if (!node.left && !node.right) {
        if (count === 0) return true;
        else return false;
    }
​
    if (node.left) {
        count -= node.left.val;
        if (traversal(node.left, count)) return true;
        count += node.left.val; //回溯
    }
    if (node.right) {
        count -= node.right.val;
        if (traversal(node.right, count)) return true;
        count += node.right.val; //回溯
    }
    return false;
}
​
var hasPathSum = function(root, targetSum) {
    if (root === null) return false;
    return traversal(root, targetSum - root.val);
};      

疊代法

代碼(C++)

//疊代(前序周遊)
class Solution1 {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        stack<TreeNode*> staNode; //用于處理節點
        stack<int> staSum; //用于處理路徑和
        if (root != nullptr) {
            staNode.push(root);
            staSum.push(root->val);
        }
        while (!staNode.empty()) {
            TreeNode* node = staNode.top();
            staNode.pop();
            int midSum = staSum.top();
            staSum.pop();
            if (node->left == nullptr && node->right == nullptr && midSum == targetSum) return true;
            if (node->right) {
                staNode.push(node->right);
                staSum.push(midSum + node->right->val);
            }
            if (node->left) {
                staNode.push(node->left);
                staSum.push(midSum + node->left->val);
            }
        }
        return false;
    }
};      

代碼(JavaScript)

//疊代
var hasPathSum = function(root, targetSum) {
    let staNode_Sum = [];
    if (root != null) {
        staNode_Sum.push(root.val); // 值先進
        staNode_Sum.push(root); //節點後進
    }
    while (staNode_Sum.length != 0) {
        let node = staNode_Sum.pop(); //節點先出
        let sum = staNode_Sum.pop(); //值後出
        if (node.left === null && node.right === null && sum === targetSum) return true;
        if (node.right) { //右
            staNode_Sum.push(sum + node.right.val); //值先進
            staNode_Sum.push(node.right); //節點後進
        }
        if (node.left) { //左
            staNode_Sum.push(sum + node.left.val); //值先進
            staNode_Sum.push(node.left); //節點後進
        }
    }
    return false;
};