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掉容器最后一个元素
    }
};

记录第一篇博客，养成好习惯
题目描述
给定一个二叉树，它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的(只能从父节点到子节点)。
二叉树不超过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