112. Path Sum

2017-02-22 · 1 min read · 前缀和

题目链接

题意：给一棵树。。问是否存在一条从树根到叶子的路径，使得路径上每个点的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;

    }
};