LeetCode 原題目網址:112. Path Sum
題目描述
給定一棵 Binary Tree 的 root
以及 targetSum
,如果這棵 Binary Tree 存在一條從 root 到 leaf 的 path,將 path 上所有 nodes 的 value 相加等於 targetSum
的話,就 return true
,否則 return false
。
題目其中有一個限制,Binary Tree 有可能為空。
解題思路
這一題可以用簡單的遞迴解決。
Base case 有兩個:
- 當
root
為NULL
時(意味 Binary Tree 為空),直接 returnfalse
。 - Binary Tree 只有一個 node 時(意味
root
其左子點跟右子點為NULL
),則看root
node 的 value 是否等於targetSum
。
下面為用 C 語言實作的程式碼:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
bool hasPathSum(struct TreeNode* root, int targetSum){
if (!root) {
return false;
}
if (root->left == NULL && root->right == NULL) {
return root->val == targetSum;
}
return hasPathSum(root->left, targetSum - root->val) || hasPathSum(root->right, targetSum - root->val);
}