Leetcode 437. Path Sum III

Path Sum III : 給定一個二叉樹和一個目標和，在樹中找到所有從根節點到葉子節點的路徑，這些路徑上所有節點值相加等於給定目標和。

Python

DFS :

DFS求解，當前節點跟目標和一致時，count加一，再對左右節點向下遍歷。

class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> int:
        if not root:
            return 0
        return self.findPath(root, sum) + self.pathSum(root.left, sum) + self.pathSum(root.right, sum)

    def findPath(self, root, sum):
        if not root:
            return 0
        count = 0
        if root.val == sum:
            count  += 1
        count  += self.findPath(root.left, sum-root.val)
        count  += self.findPath(root.right, sum-root.val)
        return count 

C++

class Solution {
public:
    int pathSum(TreeNode* root, int targetSum) {
        if (!root) return 0;  // 空節點直接返回0
        int res = 0;
        dfs(root, targetSum, res);  // 從根節點開始DFS
        res += pathSum(root->left, targetSum);   // 繼續遍歷左子樹
        res += pathSum(root->right, targetSum);  // 繼續遍歷右子樹
        return res;
    }
    
private:
    void dfs(TreeNode* node, int targetSum, int& res) {
        if (!node) return;  // 空節點直接返回
        if (node->val == targetSum) ++res;  // 找到一條路徑，計數器+1
        dfs(node->left, targetSum - node->val, res);  // 繼續遍歷左子樹
        dfs(node->right, targetSum - node->val, res);  // 繼續遍歷右子樹
    }
};