iT邦幫忙

2024 iThome 鐵人賽

0
佛心分享-刷題不只是刷題

刷經典 LeetCode 題目系列 第 76

經典LeetCode 112. Path Sum

  • 分享至 

  • xImage
  •  

Path Sum 這是一題經典的二元樹問題,測試我們對樹的遍歷與遞迴的理解。

題目:

給定一個二元樹的根節點 root 和一個整數目標值 targetSum,判斷該樹是否存在一條從根節點到葉子節點的路徑,使得這條路徑上所有節點值的總和等於目標值。

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

範例:

範例 1:

輸入:root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
輸出:true
解釋:存在一條路徑 5 -> 4 -> 11 -> 2,其總和為 22。

範例 2:

輸入:root = [1,2,3], targetSum = 5
輸出:false

範例 3:

輸入:root = [], targetSum = 0
輸出:false

實作:

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {

        if (!root) return false;

        if (!root->left && !root->right) {
            return targetSum == root->val;
        }

        int remainingSum = targetSum - root->val;
        return hasPathSum(root->left, remainingSum) || hasPathSum(root->right, remainingSum);
    }
};

參考:
#112. Path Sum


上一篇
經典LeetCode 290. Word Pattern
下一篇
經典LeetCode 222. Count Complete Tree Nodes
系列文
刷經典 LeetCode 題目80
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言