iT邦幫忙

2021 iThome 鐵人賽

DAY 26
0

問你這棵樹有沒有哪條從root到leaf的路徑,是滿足路徑上的節點加總起來等於targetsum的?

 
 

思路

呃,用Traversal,然後在找到leaf的時候,檢查此時的sum有沒有滿足,有就return true,沒有就要往上扣回到有另外一條路的部分

 
 

程式碼

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        return findPath(root, targetSum, 0);
    }
private:
    bool findPath(TreeNode* curr, int targetSum, int currSum) {
        if (curr == NULL)
            return false;
        
        if (curr->left == NULL && curr->right == NULL)
            return currSum + curr->val == targetSum? true:false;
        
        return findPath(curr->left, targetSum, currSum+curr->val) || \
              findPath(curr->right, targetSum, currSum+curr->val);
    }
};

 
 

只要在判斷時沒有真的加上去,就不用處理扣回來的問題

參考:
https://leetcode.com/problems/path-sum/discuss/1515918/C%2B%2B-beats-88-DFS


上一篇
我買開發板了
下一篇
Leetcode: 226. Invert Binary Tree
系列文
來解數學跟刷圖論跟幾何程式題或者我突然想研究的主題33
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言