首页 > 代码库 > Path Sum
Path Sum
问：二叉树是否存在路径和等于sum的路径，若存在输出true，否则输出false
分析：递归调用二叉树，每次将上一层的val值传递给子结点并加上子节点的val，当传递到某个结点为叶子结点时，判断其val值是否等于sum
错点：二叉树为空，则无论sum为多少都为false，这个容易造成RE
二叉树只有根节点，则直接判断其值与sum的关系
class Solution{public: void PathSum(TreeNode *root,int val,int sum,int &flag) { root->val+=val; if(root->left==NULL && root->right==NULL && sum==root->val) { flag=1; } if(root->left) PathSum(root->left,root->val,sum,flag); if(root->right) PathSum(root->right,root->val,sum,flag); } bool hasPathSum(TreeNode *root, int sum) { if(root==NULL) { return false; } if(root->left==NULL && root->right==NULL) { if(root->val==sum) return true; return false; } int flag=0; if(root->left) PathSum(root->left,root->val,sum,flag); if(root->right) PathSum(root->right,root->val,sum,flag); if(flag) return true; return false; }};
class Solution{public: bool PathSum(TreeNode *root,int sum,int val) { if(root==NULL) return false; val+=root->val; if(root->left==NULL && root->right==NULL) { if(sum==val) return true; return false; } return PathSum(root->left,sum,val) || PathSum(root->right,sum,val); } bool hasPathSum(TreeNode *root, int sum) { return PathSum(root,sum,0); }};
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。