首页 > 代码库 > [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 };