首页 > 代码库 > [Leetcode][Tree][Path Sum]
[Leetcode][Tree][Path Sum]
很简单的一道题,判断和为sum的路径是否存在。
结果WA了两次,一次是由于没有考虑清楚深搜停止的条件,另外一次是由于没有考虑到Path必须是从root到leaf的。
1 /** 2 * Definition for binary tree 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */10 class Solution {11 public:12 bool hasPathSum(TreeNode *root, int sum) {13 if (root == NULL) {14 return false;15 } else {16 if (sum == root->val && root->left == NULL && root->right == NULL) {17 return true;18 }19 sum -= root->val;20 return hasPathSum(root->left, sum) || hasPathSum(root->right, sum);21 }22 }23 };
第一次遇到跟题解写的思路一模一样的情况,但是题解还是比我写的更精简,更高效,减少了root==null时候的调用。
1 /** 2 * Definition for binary tree 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */10 class Solution {11 public:12 bool hasPathSum(TreeNode *root, int sum) {13 if (root == NULL) {14 return false;15 } else {16 if (root->left == NULL && root->right == NULL) {17 return sum == root->val;18 }19 sum -= root->val;20 return hasPathSum(root->left, sum) || hasPathSum(root->right, sum);21 }22 }23 };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。