Skip to content

Latest commit

 

History

History
620 lines (494 loc) · 21.4 KB

0112.路径总和.md

File metadata and controls

620 lines (494 loc) · 21.4 KB
Raw

欢迎大家参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！

递归函数什么时候需要返回值

相信很多同学都会疑惑，递归函数什么时候要有返回值，什么时候没有返回值，特别是有的时候递归函数返回类型为bool类型。那么

接下来我通过详细讲解如下两道题，来回答这个问题：

    1. 路径总和
    1. 路径总和II

112. 路径总和

题目地址：https://leetcode-cn.com/problems/path-sum/

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

示例:  给定如下二叉树，以及目标和 sum = 22，

112.路径总和1

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

思路

这道题我们要遍历从根节点到叶子节点的的路径看看总和是不是目标和。

递归

可以使用深度优先遍历的方式（本题前中后序都可以，无所谓，因为中节点也没有处理逻辑）来遍历二叉树

  1. 确定递归函数的参数和返回类型

参数：需要二叉树的根节点，还需要一个计数器，这个计数器用来计算二叉树的一条边之和是否正好是目标和，计数器为int型。

再来看返回值，递归函数什么时候需要返回值？什么时候不需要返回值？

在文章二叉树：我的左下角的值是多少？中，我给出了一个结论：

如果需要搜索整颗二叉树，那么递归函数就不要返回值，如果要搜索其中一条符合条件的路径，递归函数就需要返回值，因为遇到符合条件的路径了就要及时返回。

在二叉树：我的左下角的值是多少？中，因为要遍历树的所有路径，找出深度最深的叶子节点，所以递归函数不要返回值。

而本题我们要找一条符合条件的路径，所以递归函数需要返回值，及时返回，那么返回类型是什么呢？

如图所示：

112.路径总和

图中可以看出，遍历的路线，并不要遍历整棵树，所以递归函数需要返回值，可以用bool类型表示。

所以代码如下：

bool traversal(TreeNode* cur, int count)   // 注意函数的返回类型
  1. 确定终止条件

首先计数器如何统计这一条路径的和呢？

不要去累加然后判断是否等于目标和，那么代码比较麻烦，可以用递减，让计数器count初始为目标和，然后每次减去遍历路径节点上的数值。

如果最后count == 0，同时到了叶子节点的话，说明找到了目标和。

如果遍历到了叶子节点，count不为0，就是没找到。

递归终止条件代码如下：

if (!cur->left && !cur->right && count == 0) return true; // 遇到叶子节点，并且计数为0
if (!cur->left && !cur->right) return false; // 遇到叶子节点而没有找到合适的边，直接返回
  1. 确定单层递归的逻辑

因为终止条件是判断叶子节点，所以递归的过程中就不要让空节点进入递归了。

递归函数是有返回值的，如果递归函数返回true，说明找到了合适的路径，应该立刻返回。

代码如下：

if (cur->left) { // 左 （空节点不遍历）
    // 遇到叶子节点返回true，则直接返回true
    if (traversal(cur->left, count - cur->left->val)) return true; // 注意这里有回溯的逻辑
}
if (cur->right) { // 右 （空节点不遍历）
    // 遇到叶子节点返回true，则直接返回true
    if (traversal(cur->right, count - cur->right->val)) return true; // 注意这里有回溯的逻辑
}
return false;

以上代码中是包含着回溯的，没有回溯，如何后撤重新找另一条路径呢。

回溯隐藏在traversal(cur->left, count - cur->left->val)这里， 因为把count - cur->left->val 直接作为参数传进去，函数结束，count的数值没有改变。

为了把回溯的过程体现出来，可以改为如下代码：

if (cur->left) { // 左
    count -= cur->left->val; // 递归，处理节点;
    if (traversal(cur->left, count)) return true;
    count += cur->left->val; // 回溯，撤销处理结果
}
if (cur->right) { // 右
    count -= cur->right->val;
    if (traversal(cur->right, count - cur->right->val)) return true;
    count += cur->right->val;
}
return false;

整体代码如下：

class Solution {
private:
    bool traversal(TreeNode* cur, int count) {
        if (!cur->left && !cur->right && count == 0) return true; // 遇到叶子节点，并且计数为0
        if (!cur->left && !cur->right) return false; // 遇到叶子节点直接返回

        if (cur->left) { // 左
            count -= cur->left->val; // 递归，处理节点;
            if (traversal(cur->left, count)) return true;
            count += cur->left->val; // 回溯，撤销处理结果
        }
        if (cur->right) { // 右
            count -= cur->right->val; // 递归，处理节点;
            if (traversal(cur->right, count)) return true;
            count += cur->right->val; // 回溯，撤销处理结果
        }
        return false;
    }

public:
    bool hasPathSum(TreeNode* root, int sum) {
        if (root == NULL) return false;
        return traversal(root, sum - root->val);
    }
};

以上代码精简之后如下：

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

是不是发现精简之后的代码，已经完全看不出分析的过程了，所以我们要把题目分析清楚之后，在追求代码精简。 这一点我已经强调很多次了！

迭代

如果使用栈模拟递归的话，那么如果做回溯呢？

此时栈里一个元素不仅要记录该节点指针，还要记录从头结点到该节点的路径数值总和。

C++就我们用pair结构来存放这个栈里的元素。

定义为：pair<TreeNode*, int> pair<节点指针，路径数值>

这个为栈里的一个元素。

如下代码是使用栈模拟的前序遍历，如下：（详细注释）

class Solution {

public:
    bool hasPathSum(TreeNode* root, int sum) {
        if (root == NULL) return false;
        // 此时栈里要放的是pair<节点指针，路径数值>
        stack<pair<TreeNode*, int>> st;
        st.push(pair<TreeNode*, int>(root, root->val));
        while (!st.empty()) {
            pair<TreeNode*, int> node = st.top();
            st.pop();
            // 如果该节点是叶子节点了，同时该节点的路径数值等于sum，那么就返回true
            if (!node.first->left && !node.first->right && sum == node.second) return true;

            // 右节点，压进去一个节点的时候，将该节点的路径数值也记录下来
            if (node.first->right) {
                st.push(pair<TreeNode*, int>(node.first->right, node.second + node.first->right->val));
            }

            // 左节点，压进去一个节点的时候，将该节点的路径数值也记录下来
            if (node.first->left) {
                st.push(pair<TreeNode*, int>(node.first->left, node.second + node.first->left->val));
            }
        }
        return false;
    }
};

如果大家完全理解了本地的递归方法之后，就可以顺便把leetcode上113. 路径总和II做了。

113. 路径总和II

题目地址：https://leetcode-cn.com/problems/path-sum-ii/

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。

示例: 给定如下二叉树，以及目标和 sum = 22，

113.路径总和II1.png

思路

113.路径总和II要遍历整个树，找到所有路径，所以递归函数不要返回值！

如图：

113.路径总和II

为了尽可能的把细节体现出来，我写出如下代码（这份代码并不简洁，但是逻辑非常清晰）

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    // 递归函数不需要返回值，因为我们要遍历整个树
    void traversal(TreeNode* cur, int count) {
        if (!cur->left && !cur->right && count == 0) { // 遇到了叶子节点且找到了和为sum的路径
            result.push_back(path);
            return;
        }

        if (!cur->left && !cur->right) return ; // 遇到叶子节点而没有找到合适的边，直接返回

        if (cur->left) { // 左 （空节点不遍历）
            path.push_back(cur->left->val);
            count -= cur->left->val;
            traversal(cur->left, count);    // 递归
            count += cur->left->val;        // 回溯
            path.pop_back();                // 回溯
        }
        if (cur->right) { // 右 （空节点不遍历）
            path.push_back(cur->right->val);
            count -= cur->right->val;
            traversal(cur->right, count);   // 递归
            count += cur->right->val;       // 回溯
            path.pop_back();                // 回溯
        }
        return ;
    }

public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        result.clear();
        path.clear();
        if (root == NULL) return result;
        path.push_back(root->val); // 把根节点放进路径
        traversal(root, sum - root->val);
        return result;
    }
};

至于113. 路径总和II 的迭代法我并没有写，用迭代方式记录所有路径比较麻烦，也没有必要，如果大家感兴趣的话，可以再深入研究研究。

总结

本篇通过leetcode上112. 路径总和 和 113. 路径总和II 详细的讲解了 递归函数什么时候需要返回值，什么不需要返回值。

这两道题目是掌握这一知识点非常好的题目，大家看完本篇文章再去做题，就会感受到搜索整棵树和搜索某一路径的差别。

对于112. 路径总和，我依然给出了递归法和迭代法，这种题目其实用迭代法会复杂一些，能掌握递归方式就够了！

其他语言版本

Java：

class Solution {
   public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        targetSum -= root.val;
        // 叶子结点
        if (root.left == null && root.right == null) {
            return targetSum == 0;
        }
        if (root.left != null) {
            boolean left = hasPathSum(root.left, targetSum);
            if (left) {// 已经找到
                return true;
            }
        }
        if (root.right != null) {
            boolean right = hasPathSum(root.right, targetSum);
            if (right) {// 已经找到
                return true;
            }
        }
        return false;
    }
}

// LC112 简洁方法
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        
        if (root == null) return false; // 为空退出
        
        // 叶子节点判断是否符合
        if (root.left == null && root.right == null) return root.val == targetSum;

        // 求两侧分支的路径和
        return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
    }
}

迭代

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root==null)return false;
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        stack1.push(root);stack2.push(root.val);
        while(!stack1.isEmpty()){
            int size = stack1.size();
            for(int i=0;i<size;i++){
                TreeNode node = stack1.pop();int sum=stack2.pop();
                // 如果该节点是叶子节点了，同时该节点的路径数值等于sum，那么就返回true
                if(node.left==null && node.right==null && sum==targetSum)return true;
                // 右节点，压进去一个节点的时候，将该节点的路径数值也记录下来
                if(node.right!=null){
                    stack1.push(node.right);stack2.push(sum+node.right.val);
                }
                // 左节点，压进去一个节点的时候，将该节点的路径数值也记录下来
                if(node.left!=null){
                    stack1.push(node.left);stack2.push(sum+node.left.val);
                }
            }
        }
        return false;
    }   
    
}

0113.路径总和-ii

class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res; // 非空判断
        
        List<Integer> path = new LinkedList<>();
        preorderDFS(root, targetSum, res, path);
        return res;
    }

    public void preorderDFS(TreeNode root, int targetSum, List<List<Integer>> res, List<Integer> path) {
        path.add(root.val);
        // 遇到了叶子节点
        if (root.left == null && root.right == null) {
            // 找到了和为 targetSum 的路径
            if (targetSum - root.val == 0) {
                res.add(new ArrayList<>(path));
            }
            return; // 如果和不为 targetSum，返回
        }

        if (root.left != null) {
            preorderDFS(root.left, targetSum - root.val, res, path);
            path.remove(path.size() - 1); // 回溯
        }
        if (root.right != null) {
            preorderDFS(root.right, targetSum - root.val, res, path);
            path.remove(path.size() - 1); // 回溯
        }
    }
}

Python：

0112.路径总和

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

// 递归法

class Solution:
    def hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
        def isornot(root,targetSum)->bool:
            if (not root.left) and (not root.right) and targetSum == 0:return True // 遇到叶子节点，并且计数为0
            if (not root.left) and (not root.right):return False //遇到叶子节点，计数不为0
            if root.left:
                targetSum -= root.left.val  //左节点
                if isornot(root.left,targetSum):return True  //递归，处理左节点
                targetSum += root.left.val  //回溯
            if root.right:
                targetSum -= root.right.val //右节点
                if isornot(root.right,targetSum):return True //递归，处理右节点
                targetSum += root.right.val //回溯
            return False
            
        if root == None:return False  //别忘记处理空TreeNode
        else:return isornot(root,targetSum-root.val)

0113.路径总和-ii

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
//递归法
class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:
        path=[]
        res=[]
        def pathes(root,targetSum):
            if (not root.left) and (not root.right) and targetSum == 0: // 遇到叶子节点，并且计数为0
                res.append(path[:])  //找到一种路径，记录到res中，注意必须是path[:]而不是path
                return 
            if (not root.left) and (not root.right):return // 遇到叶子节点直接返回
            if root.left:   //左
                targetSum -= root.left.val
                path.append(root.left.val)     //递归前记录节点
                pathes(root.left,targetSum)    //递归
                targetSum += root.left.val     //回溯
                path.pop()                     //回溯
            if root.right:  //右
                targetSum -= root.right.val
                path.append(root.right.val)    //递归前记录节点
                pathes(root.right,targetSum)   //递归
                targetSum += root.right.val    //回溯
                path.pop()                     //回溯
            return
            
        if root == None:return []             //处理空TreeNode
        else:
            path.append(root.val)             //首先处理根节点
            pathes(root,targetSum-root.val)
            return res

Go：

JavaScript：

0112.路径总和

/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {boolean}
 */
let hasPathSum = function (root, targetSum) {
  // 递归法
  const traversal = (node, cnt) => {
    // 遇到叶子节点，并且计数为0
    if (cnt === 0 && !node.left && !node.right) return true;
    // 遇到叶子节点而没有找到合适的边(计数不为0)，直接返回
    if (!node.left && !node.right) return false;

    //  左（空节点不遍历）.遇到叶子节点返回true，则直接返回true
    if (node.left && traversal(node.left, cnt - node.left.val)) return true;
    //  右（空节点不遍历）  
    if (node.right && traversal(node.right, cnt - node.right.val)) return true;
    return false;
  };
  if (!root) return false;
  return traversal(root, targetSum - root.val);

  // 精简代码:
  // if (!root) return false;
  // if (!root.left && !root.right && targetSum === root.val) return true;
  // return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
};

0113.路径总和-ii

let pathSum = function (root, targetSum) {
  // 递归法
  // 要遍历整个树找到所有路径，所以递归函数不需要返回值, 与112不同
  const res = [];
  const travelsal = (node, cnt, path) => {
    // 遇到了叶子节点且找到了和为sum的路径
    if (cnt === 0 && !node.left && !node.right) {
      res.push([...path]); // 不能写res.push(path), 要深拷贝
      return;
    }
    if (!node.left && !node.right) return; // 遇到叶子节点而没有找到合适的边，直接返回
    // 左 （空节点不遍历）
    if (node.left) {
      path.push(node.left.val);
      travelsal(node.left, cnt - node.left.val, path); // 递归
      path.pop(); // 回溯
    }
    // 右 （空节点不遍历）
    if (node.right) {
      path.push(node.right.val);
      travelsal(node.right, cnt - node.right.val, path); // 递归
      path.pop(); // 回溯
    }
    return;
  };
  if (!root) return res;
  travelsal(root, targetSum - root.val, [root.val]); // 把根节点放进路径
  return res;
};

0112 路径总和

var hasPathSum = function(root, targetSum) {
    //递归方法
    // 1. 确定函数参数
    const traversal = function(node,count){
        // 2. 确定终止条件
        if(node.left===null&&node.right===null&&count===0){
            return true;
        }
        if(node.left===null&&node.right===null){
            return false;
        }
        //3. 单层递归逻辑
        if(node.left){
            if(traversal(node.left,count-node.left.val)){
                return true;
            }
        }
        if(node.right){
            if(traversal(node.right,count-node.right.val)){
                return true;
            }
        }
        return false;
    }
    if(root===null){
        return false;
    }
    return traversal(root,targetSum-root.val);
};

113 路径总和

var pathSum = function(root, targetSum) {
    //递归方法
    let resPath = [],curPath = [];
    // 1. 确定递归函数参数
    const travelTree = function(node,count){
        curPath.push(node.val);
        count-=node.val;
        if(node.left===null&&node.right===null&&count===0){
            resPath.push([...curPath]);
        }
        node.left&&travelTree(node.left,count);
        node.right&&travelTree(node.right,count);
        let cur = curPath.pop();
        count-=cur;
    }
    if(root===null){
        return resPath;
    }
    travelTree(root,targetSum);
    return resPath;
};