題目： LeetCode - 112. Path Sum

題目說明

給一個 Binary Tree 及整數 sum，求是否有一段從樹根到葉子的總和會等於 sum。

解題思路

使用遞迴的觀念遍歷整棵樹，curSum 紀錄從樹根遍歷到這裡的總和，若是到了葉子且 curSum == sum 回傳 True，否則回傳 hasPathSum(root->left, sum, curSum) || hasPathSum(root->right, sum, curSum)

參考解法

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum, int curSum = 0) // add curSum
    {
        if(!root) return false;
        curSum += root->val;
        if(!root->left && !root->right && curSum == sum) return true;
        return hasPathSum(root->left, sum, curSum) || hasPathSum(root->right, sum, curSum);
    }
};