是否存在根到叶节点的和等于给定数。
思路：递归。判断左儿子或右儿子是否存在这一路径（sum变为sum-root->val）。
ver0：递归到最后会是叶节点的左右儿子，所以要有root==NULL的判断
1 class Solution { 2 public: 3 bool hasPathSum(TreeNode* root, int sum) { 4 if(root==NULL){//ERROR 5 if(sum == 0) return true; 6 else return false; 7 } 8 // if(sum < root->val) return false; 9 return hasPathSum(root->left,sum-root->val) || hasPathSum(root->right,sum-root->val);10 }11 }; WA:
Output:true
Expected:false
ver1：原始树是否为空另外判断。
1 class Solution { 2 public: 3 bool hasPathSum(TreeNode* root, int sum) { 4 if(root==NULL) return false; 5 return help(root,sum); 6 7 } 8 9 bool help(TreeNode* root, int sum){10 if(root==NULL){11 if(sum == 0) return true;12 else return false;13 }14 // if(sum < root->val) return false;15 return help(root->left,sum-root->val) || help(root->right,sum-root->val);//ERROR16 }17 }; WA:
Input:[1,2] 1
Output:true
Expected:false
将只有一个儿子的节点误当作叶节点。
ver2：
1 class Solution { 2 public: 3 bool hasPathSum(TreeNode* root, int sum) { 4 if(root==NULL) return false; 5 return help(root,sum); 6 7 } 8 9 bool help(TreeNode* root, int sum){10 if(root==NULL){11 if(sum == 0) return true;12 else return false;13 }14 // if(sum < root->val) return false;15 16 if(root->left && root->right) return help(root->left,sum-root->val) || help(root->right,sum-root->val);17 if(root->left) return help(root->left,sum-root->val);18 if(root->right) return help(root->right,sum-root->val); //leaf-node:19 if(sum == 0) return true;//ERROR20 return false;21 22 }23 }; WA:
Input:[1] 1
Output:false
Expected:true
叶节点的情况下判断错误（即sum==0），应为sum==root->val。
ver3：
1 class Solution { 2 public: 3 bool hasPathSum(TreeNode* root, int sum) { 4 if(root==NULL) return false; 5 return help(root,sum); 6 7 } 8 9 bool help(TreeNode* root, int sum){10 // if(root==NULL){11 // if(sum == 0) return true;12 // else return false;13 // }14 // if(sum < root->val) return false;15 16 if(root->left && root->right) return help(root->left,sum-root->val) || help(root->right,sum-root->val);17 if(root->left) return help(root->left,sum-root->val);18 if(root->right) return help(root->right,sum-root->val);19 if(sum == root->val) return true;20 return false;21 22 }23 };
别人的简洁版代码：
1 class Solution { 2 public: 3 bool hasPathSum(TreeNode* root, int sum) { 4 if(root==NULL) 5 return false; 6 if(root->val == sum && root->left == NULL && root->right == NULL) 7 return true; 8 return hasPathSum(root->left, sum-root->val) || hasPathSum(root->right, sum-root->val); 9 }10 }; 递归到最后传入的是叶节点而非其左右儿子，所以不必另开help函数。
如果是只有一个儿子的节点，也可处理（落入root==NULL的判断内）。