Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：给一棵树。。问是否存在一条从树根到叶子的路径，使得路径上每个点的val之和等于给定的sum。
思路：。。。直接搞就好。。。由于是比较经典的题目所以记录一下。。。注意递归的时候每一部分都要返回值orz..(我是多久没写代码了。。。
1/**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 * int val;
5 * TreeNode *left;
6 * TreeNode *right;
7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8 * };
9 */
10class Solution {
11public:
12 bool leaf(TreeNode* root)
13 {
14 if (root->left==NULL&&root->right==NULL) return true;
15 return false;
16 }
17 int SUM;
18 bool dfs(TreeNode* root,int cur)
19 {
20 // cout<<"val:"<<root->val<<" cur:"<<cur<<endl;
21 bool ret=false;
22 if (cur+root->val==SUM&&leaf(root)) return true;
23 if (root->left!=NULL) ret = dfs(root->left,cur+root->val);
24 if (ret) return true;
25 if (root->right!=NULL) ret = dfs(root->right,cur+root->val);
26 if (ret) return true;
27 return false;
28 }
29 bool hasPathSum(TreeNode* root, int sum) {
30 if (root==NULL) return false;
31 SUM = sum;
32 bool res = dfs(root,0);
33 return res;
34
35 }
36};