HackMD
【LeetCode】 112. Path Sum
Description
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
Note: A leaf is a node with no children.
給一個二元樹和一個總和值，判斷這棵樹有沒有一條從頭到葉的路徑總和剛好為總和值。
注意：一個葉節點沒有小孩。
Example:
Example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
Solution
- 只要注意葉節點必須沒有左子樹和右子樹就好了，接下來就直接照一般DFS去跑所有路徑即可。
Code
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool hasPathSum(TreeNode* root, int sum) {
if(!root)return false;
sum -= root->val;
if(!root->left && !root->right)
{
if(sum==0)return true;
}
if(hasPathSum(root->left,sum))
return true;
if(hasPathSum(root->right,sum))
return true;
return false;
}
};
