LeetCode:112. Path Sum

问题描述：

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example: Given the below binary tree and  sum = 22 , 5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

分析：

题目中没有交代清的三个问题：

1.root-to-leaf 路径，必须是根节点到叶子节点的路径。

2.节点值可以为负数。

3.空的二叉树，不可以视为存在和为0的路劲。

AC代码：

bool hasPathSum(TreeNode * root,int expectSum,int currentSum) { currentSum+=root->val; bool isLeaf = (root->left == NULL && root->right == NULL); if(isLeaf && (currentSum == expectSum)) return true; bool left = false; bool right = false; if(root->left != NULL) left = hasPathSum(root->left,expectSum,currentSum); if(root->right != NULL) right = hasPathSum(root->right,expectSum,currentSum); //return false; return left || right ; } bool hasPathSum(TreeNode* root, int sum) { if(root == NULL) return false; int currentSum = 0; return hasPathSum(root,sum,currentSum); }

在网上还看到了一个递归解决的答案，代码很简洁，可供学习。

bool hasPathSum(TreeNode *root, int sum) { if (root == NULL) return false; else if (root->left == NULL && root->right == NULL && root->val == sum) return true; else { return hasPathSum(root->left, sum-root->val) || hasPathSum(root->right, sum - root->val); } }