LeetCode双重递归
 
记录第一篇博客，养成好习惯
题目描述
题解
思路
代码（Python实现）
  
 

 
记录第一篇博客，养成好习惯
 
题目描述
 
给定一个二叉树，它的每个结点都存放着一个整数值。
 
找出路径和等于给定数值的路径总数。
 
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
 
二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
 
示例：
 
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
 
10
 / 
 5 -3
 / \ 
 3 2 11
 / \ 
 3 -2 1
 
返回 3。和等于 8 的路径有:
 
5 -> 3
5 -> 2 -> 1
-3 -> 11
 
来源：力扣（LeetCode）
 链接：https://leetcode-cn.com/problems/path-sum-iii
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 
题解
 
思路
 
1.在题干的描述中难点在于路径不需要从根节点开始，也不需要在叶子节点结束
 
1）不妨先考虑路径必须要从根节点开始再到叶节点结束，记录路径中满足sum的路径和，这就会构成第一层递归
 
此时遍历在叶节点结束，但构成sum的路径不一定结束在叶节点
 
2）将每个遍历到的节点都看作根节点，则构成第二层递归
 
此时每个遍历到的节点，则会实现不一定从根节点出发
 
代码（Python实现）
 
class Solution(object):

    #第一层递归，类似于树的中序遍历
    #实现：让遍历到的每个节点，依次作为根节点
    def pathSum(self, root, sum):
        pathNum=0
        if root!=None and root.val!=None:
            pathNum=pathNum+self.fun(root,sum)
            pathNum=pathNum+self.pathSum(root.left,sum)
            pathNum=pathNum+self.pathSum(root.right,sum)
        return pathNum


    #第二层递归
    #实现：找出从root节点出发到叶节点过程中，和为tempSum的路径总和
    #（注意此处的tempSum与题干中要求的sum并不相同）
    def fun(self,root,tempSum):
        pathNum=0
        if root!=None:
            tempSum=tempSum-root.val
            if tempSum==0:
                #此时可能还未到达叶节点
                pathNum=pathNum+1
                
            pathNum=pathNum+
            	self.fun(root.left,tempSum)+
            	self.fun(root.right,tempSum)
        return pathNum

1.
 
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
 
/**
  * Definition for binary tree
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  * };
  */
 class Solution {
 public:
     bool dfs(TreeNode *node, int sum, int curSum)
     {
         if (node == NULL)
             return false;
         
         if (node->left == NULL && node->right == NULL)
             return curSum + node->val == sum;
                
         return dfs(node->left, sum, curSum + node->val) || dfs(node->right, sum, curSum + node->val);
     }
     
     bool hasPathSum(TreeNode *root, int sum) {
         
         return dfs(root, sum, 0);
     }
 };
 
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
  * };
 */
bool dfs(struct TreeNode *node, int sum, int cur);
bool hasPathSum(struct TreeNode *root, int sum) {
    return dfs(root, sum, 0);
}

bool dfs(struct TreeNode *node, int sum, int cur){
    if(node == NULL) return false;
    if(node->left == NULL && node->right == NULL)
        return cur+node->val == sum;
    return(dfs(node->left, sum, cur+node->val) || dfs(node->right, sum, cur+node->val));
}
 
2.路径和，打印路径
 
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
 
For example:
 Given the below binary tree and sum = 22,
 
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
 
return
 
[
   [5,4,11,2],
   [5,8,4,5]
]

这道二叉树路径之和在之前的基础上又需要找出路径 ，但是基本思想都一样，还是需要用深度优先搜索DFS，只不过数据结构相对复杂一点，需要用到二维的vector，而且每当DFS搜索到新节点时，都要保存该节点。而且每当找出一条路径之后，都将这个保存为一维vector的路径保存到最终结果二位vector中。并且，每当DFS搜索到子节点，发现不是路径和时，返回上一个结点时，需要把该节点从一维vector中移除。代码如下：
 
class Solution {
public:
    vector<vector<int> > pathSum(TreeNode *root, int sum) {
        vector<vector<int>> res;
        vector<int> out;
        helper(root, sum, out, res);
        return res;
    }
    void helper(TreeNode* node, int sum, vector<int>& out, vector<vector<int>>& res) {
        if (!node) return;
        out.push_back(node->val);
        if (sum == node->val && !node->left && !node->right) {
            res.push_back(out);
        }
        helper(node->left, sum - node->val, out, res);
        helper(node->right, sum - node->val, out, res);
        out.pop_back();
    }
};
 
3.没必要从开始到叶子节点结束，任意路径和。
 
You are given a binary tree in which each node contains an integer value.
 
Find the number of paths that sum to a given value.
 
The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).
 
The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.
 
Example:
 
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11
 
这道题让我们求二叉树的路径的和等于一个给定值，说明了这条路径不必要从根节点开始，可以是中间的任意一段，而且二叉树的节点值也是有正有负。那么我们可以用递归来做，相当于先序遍历二叉树，对于每一个节点都有记录了一条从根节点到当前节点到路径，同时用一个变量curSum记录路径节点总和，然后我们看curSum和sum是否相等，相等的话结果res加1，不等的话我们来继续查看子路径和有没有满足题意的，做法就是每次去掉一个节点，看路径和是否等于给定值，注意最后必须留一个节点，不能全去掉了，因为如果全去掉了，路径之和为0，而如果假如给定值刚好为0的话就会有问题，整体来说不算一道很难的题，参见代码如下：
 
class Solution {
public:
    int pathSum(TreeNode* root, int sum) {
        int res = 0;
        vector<TreeNode*> out;
        helper(root, sum, 0, out, res);
        return res;
    }
    void helper(TreeNode* node, int sum, int curSum, vector<TreeNode*>& out, int& res) {
        if (!node) return;
        curSum += node->val;
        out.push_back(node);
        if (curSum == sum) ++res;
        int t = curSum;
        for (int i = 0; i < out.size() - 1; ++i) {
            t -= out[i]->val;
            if (t == sum) ++res;
        }
        helper(node->left, sum, curSum, out, res);
        helper(node->right, sum, curSum, out, res);
        out.pop_back();
    }
};
 
 

Path Sum
 
 
1、题目
 

  
 
 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.
 
 
 
 
2、分析
 

 这道题很简单，用递归
 

 代码一目了然
 

 
 
 
3、代码
 

 
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode *root, int sum) {
        if(!root) return false;         //空树，返回false   
        if(!root->left && !root->right)  return root->val==sum;      //左右子树均为空，判断val是否等于sum
        return hasPathSum(root->left,sum-root->val) || hasPathSum(root->right,sum-root->val);    //递归调用hasPathSum函数
    }
};
 
 
 
 
 
Path Sum II
 
 
1、题目
 

  
 
 Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
 
 For example:
 
 
 Given the below binary tree and 
 sum = 22
 , 
 
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
 
 
 return
 
 
 
[
   [5,4,11,2],
   [5,8,4,5]
]
 
 
 
 
2、分析
 

 
 
 

 递归法，对递归函数执行的逻辑要理清，画图模拟一遍有帮助于理解程序的执行流程
 
3、代码
 

 
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int> > pathSum(TreeNode *root, int sum) {
        vector< vector<int> > result;
        vector<int> current;
        pathSum(root,sum,current,result);
        return result;
    }
private:
    void pathSum(TreeNode *root,int sum,vector<int> current,vector<vector<int>> &result)
    //必须用引用&，否则传递过来的只是current、result的副本，函数递归调用结束后，这些副本在栈里面被释放掉，并未真正改变current、result
    {
        if(!root)  return;
        
        current.push_back(root->val);
        if(!root->left && !root->right)  
        {
            if(sum==root->val)   
              result.push_back(current);
        }
        
        pathSum(root->left,sum-root->val,current,result);
        pathSum(root->right,sum-root->val,current,result);
        
       current.pop_back();     //pop掉容器最后一个元素
    }
};
 
 
 
 

题目描述
 
给定一个二叉树和一个值sum，判断是否有从根节点到叶子节点的节点值之和等于sum的路径，
 
例如：
 
给出如下的二叉树，sum=22，
 
              5↵             / ↵            4   8↵           /   / ↵          11  13  4↵         /      / ↵        7    2  5   1
 
返回true，因为存在一条路径5->4->11->2的节点值之和为22
 
 
 
思路：DFS  当到达叶子节点时，判断是否等于sum  是就及时返回   不是继续搜索
 
bool hasPathSum(TreeNode* root, int sum) {
        // write code here
        if(root==NULL)
        {
            
                return false;
        }
        if(root->left==NULL && root->right==NULL) //到达叶子节点
        {
            if(root->val==sum)
                return true;
            else
                return false;
        }
        if(root->left!=NULL)
        {
            if(hasPathSum(root->left,sum-root->val))  //左子树有满足条件的
                return true;
        }
        if(root->right!=NULL)
        {
            if(hasPathSum(root->right,sum-root->val))
                return true;
        }
        return false;//都没有找到
        
        
        
    }
 
进一步：返回所有的满足sum的路径
 
思路：同样采用DFS遍历  若满足 存入全局的res答案中
 
 vector<vector<int>> res;
    
    vector<vector<int> > pathSum(TreeNode* root, int sum) {
        // write code here
        
        vector<int> path;
        DFS(root,sum,path);
        return res;
        
    }
    
    void DFS(TreeNode* root,int sum,vector<int> path)
    {
        if(root==NULL)
            return;
        path.push_back(root->val);//路径加入当前节点
        if(root->left==NULL && root->right==NULL) //到达根节点
        {
            if(sum==root->val)//满足
            {
                res.push_back(path);//存入答案中
                
            }
        }
      DFS(root->left,sum-root->val,path);
      DFS(root->right,sum-root->val,path);
       
        
    }