Leetcode112

思路

思路

采用递归依次对路径求和，给出错误思路代码：

class Solution { public: bool hasPathSum(TreeNode* root, int sum) { return Sum(root, sum); } int num = 0; bool Sum(TreeNode* tree, int sum) { if(tree) num += tree->val; return (!tree->left && !tree->right && sum == num) || (tree->left && Sum(tree->left, sum)) || (tree->right && Sum(tree->right, sum)); } };

总结&纠错： 1.可以直接在hasPathSum的基础上进行迭代，无需新建其他成员函数； 2.return语句存在错误，在求和过程中，不同路径下应该扣除其他分支路径的值，否则只会越加越大。

修改代码： 1.自身迭代即可：

class Solution1 { public: bool hasPathSum(TreeNode *root, int sum) { ...... } };

首先，判断特殊情况

class Solution1 { public: bool hasPathSum(TreeNode *root, int sum) { if (root == nullptr) { return false; ...... } } };

只有节点为叶子节点时，才考虑判断求和，**注意：**这里的返回值使用sum == root->val;去给出判断后返回，若将判断加到if语句中if(!root->left && !root->right && sum == root->val) return true;还需额外添加判断，学习简化思路！ 依次减掉路径上的val值避免不同分支的影响。

参考答案：

class Solution { public: bool hasPathSum(TreeNode *root, int sum) { if (root == nullptr) { return false; } if (root->left == nullptr && root->right == nullptr) { return sum == root->val; } return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val); } };

重新修改自己的代码：

class Solution { public: bool hasPathSum(TreeNode* root, int sum) { if(!root) return false; return Sum(root, sum); } bool Sum(TreeNode* tree, int sum) { return (!tree->left && !tree->right && sum == tree->val) || (tree->left && Sum(tree->left, sum- tree->val)) || (tree->right && Sum(tree->right, sum - tree->val)); } };

(若题目说明全为正数，则可以在求和超过sum时提前结束。添加if(sum < 0) return false即可)

同样可以使用广度优先搜索，以队列的方式判断。