112. Path Sum

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.

For example:
Given the below binary tree andsum = 22,

5/\48//\11134/\\721

return true, as there exist a root-to-leaf path5->4->11->2which sum is 22.


思路：

使用递归先序遍历。

代码如下：

/***Definitionforabinarytreenode.*structTreeNode{*intval;*TreeNode*left;*TreeNode*right;*TreeNode(intx):val(x),left(NULL),right(NULL){}*};*/classSolution{public:boolhasPathSum(TreeNode*root,intsum){if(NULL==root)returnfalse;returnDFS(root,0,sum);}boolDFS(TreeNode*root,intcurTotal,intsum){if(NULL==root)returnfalse;curTotal+=root->val;if(!root->left&&!root->right&&(curTotal==sum))returntrue;elsereturnDFS(root->left,curTotal,sum)||DFS(root->right,curTotal,sum);}};


其他做法：

boolhasPathSum(TreeNode*root,intsum){if(root==NULL)returnfalse;elseif(root->left==NULL&&root->right==NULL&&root->val==sum)returntrue;else{returnhasPathSum(root->left,sum-root->val)||hasPathSum(root->right,sum-root->val);}}

参考自：http://blog.csdn.net/booirror/article/details/42680111

2016-08-07 13:17:42