LeetCode : 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

首先我的想法是递归，从root节点开始，一直遍历到各个leaf节点，计算各条路径的sum。
开始的递归代码如下:

1 int addToSum(TreeNode* root,int result){
2        if(root==NULL)  return 0;
3        addToSum(root->left,result);
4        result+=root->val;
5 }       

这段递归有点问题：首先只是计算root的左节点路径的Sum，如上图：是5->4->11->7这条路径的值。最主要的是这种递归是先递归下降，下降到leaf节点，再递归上升，上升到root节点后，才能计算出result的值。

改进该代码:

1 bool addToSum(TreeNode* root,int sum){
2         if(root==NULL) return false;
3         int sumLeft=sum-root->val;
4         addToSum(root->left,sumLeft);
5         return root->val==sum;
6 }    

这样当到达leaf节点时，就可以马上知道该条路径是不是等于Sum。但是由于递归的性质，栈帧的存在，bool值仍然要一级一级往上传递，这个意义上与上面的代码没有什么区别。

原本想通过bool值来改变递归路径，例如：5->4->11->7这条路径，由7这个节点返回false，到达11这个节点，转而向右子树搜索。但是目前没有找到方法。

还有一点第5行代码：

1    return root->val==sum;  

改成

1    return root->val==sumLeft;

可以吗？不可以。

sumLeft是本栈帧的数据代表的是本节点下的子节点之和，而sum是上一栈帧传递过来的数据，代表的是root节点的子节点之和；

当sum==27时，5->4->11->7这条路径，递归到7这个节点时，sumLeft==sum-7==0; sum==7;

但是上面的改进后的代码还不能正确的返回，当到达节点11时，sum==18(11+7); 返回的是false;

我们应该改进递归的次序，当到达7这个节点时，返回的true，传递到上一栈帧中，没起到任何作用，被无情丢失了。

1 bool addToSum(TreeNode* root, int sum){
2        if (root == NULL) return false;
3        if (root->val == sum)
4        return true;
5        addToSum(root->left, sum - root->val);
6 }

我在VS2013中看到，当到达7这个节点，返回true后，竟然直接的跳过了前面的3个栈帧。

回到刚刚的改变路径问题，第一种递归方法的true和false不能真正代表本节点的真实情况，而且整个方法返回的都是false。第二种递归方法，直接就跳过了其余栈帧。

还有一个重要的问题，搜索方向的问题，以上的递归都是左子树搜索的，根本没有搜索右子树。

可以从节点出发，只是比较节点是否符合要求，然后由递归来控制方向，递归的方向。

最终版：

1  bool hasPathSum(TreeNode *root, int sum) {
2       if(root==NULL) return false;
3       if(root->left==NULL && root->right==NULL && root->val==sum)
4           return true;
5       return(hasPathSum(root->left,sum-root->val) || hasPathSum(root->right,sum-root->val));
6 }

中间还写过一个版本：

 1 bool hasPathSum1(TreeNode *root, int sum) {
 2      if (root == NULL) return false;
 3          hasPathSum1(root->left, sum - root->val);
 4      if (root->val == sum)
 5          return true;
 6       else
 7           hasPathSum1(root->right, sum - root->val);
 8 }

这个版本企图改变递归的路径。

这种不跳过递归帧的返回方式，得到的肯定不是正确的结果；还有一点，这种方式的递归，没有对各个递归路径的结果进行归纳终结，导致结果是最后一条递归路径的结果。

LeetCode : Path Sum

原文：http://www.cnblogs.com/coder-chen/p/4356969.html