Q: 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 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.
A: 深度搜索。注意节点的val值有正有负,原先以为节点值都为正数,做了个剪枝:root->val>sum.
bool hasPathSum(TreeNode *root, int sum) { // Start typing your C/C++ solution below // DO NOT write int main() function if(root==NULL) return false; if(root->val==sum&&!root->left&&!root->right) return true; else return hasPathSum(root->left,sum-root->val)||hasPathSum(root->right,sum-root->val); }
原文链接: https://www.cnblogs.com/summer-zhou/archive/2013/06/03/3116076.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/90992
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!