路径总和 II（ LeetCode 113 ）

一、题目描述

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

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 路径总和 II（ LeetCode 113 ）: https://leetcode-cn.com/problems/path-sum-ii/
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {

        // 构建一个 value，用来计算当前路径下节点的总和
        int value = 0;

        // 构建一个 path，用来记录满足条件的路径
        List<List<Integer>> path = new LinkedList<>();

        // 构建一个栈，用来保存当前路径下的节点
        Stack<Integer> stack = new Stack<>();

        // 从根节点开始搜索
        search(root,value,targetSum,stack,path);

        // 返回满足条件的路径
        return path;

    }

    // node 为正在遍历的节点
    // value 为栈中各个节点值的总和
    // targetSum 为目标路径的和
    // stack 存储该路径上的所有节点
    // path 存储满足条件，即路径上的各个节点之和为 targetSum 的那些路径
    private void search(TreeNode node,int value,int targetSum ,Stack<Integer> stack,List<List<Integer>> path){

            // 如果节点为空，那么就不需要再访问下去了
            if(node == null) return;

            // 将当前访问节点的值累加到 value 上
            value += node.val;

            // 把当前的节点值添加到栈中，栈中保存的就是从根节点到当前节点的路径
            stack.push(node.val);

            // 如果当前节点的左子树为空
            // 并且当前节点的右子树也为空
            // 即当前节点为叶子节点
            // 同时当前路径下的节点值之和 value 与目标值 targetSum 相等
            // 说明找到了一条符合条件的路径
            if(node.left == null && node.right == null && value == targetSum){

                // 把这条路径添加到 path 中
                path.add(new LinkedList<>(stack));
            }

            // 继续递归的搜索当前节点 node 的左子树
            search(node.left,value,targetSum,stack,path);

            // 继续递归的搜索当前节点 node 的右子树
            search(node.right,value,targetSum,stack,path);

            // 搜索完当前节点的左右子树之后，当前节点已经完成了访问，需要返回到它的父节点
            // 所以 value 减去当前节点的值
            value -= node.val;

            // 栈也弹出当前的节点值
            stack.pop();

    }
}

2、C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 路径总和 II（ LeetCode 113 ）: https://leetcode-cn.com/problems/path-sum-ii/
class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {

        // 构建一个 value，用来计算当前路径下节点的总和
        int value = 0;

        // 构建一个 path，用来记录满足条件的路径
        vector<vector<int>> path;

        // 构建一个栈，用来保存当前路径下的节点
        stack<int> st;

        // 从根节点开始搜索
        search(root,value,targetSum,st,path);

        // 返回满足条件的路径
        return path;

    }

    // node 为正在遍历的节点
    // value 为栈中各个节点值的总和
    // targetSum 为目标路径的和
    // st 存储该路径上的所有节点
    // path 存储满足条件，即路径上的各个节点之和为 targetSum 的那些路径
    void search(TreeNode* node, int value, int targetSum, stack<int> st, vector<vector<int>> &path){

            // 如果节点为空，那么就不需要再访问下去了
            if(node == NULL) return;

            // 将当前访问节点的值累加到 value 上
            value += node->val;

            // 把当前的节点值添加到栈中，栈中保存的就是从根节点到当前节点的路径
            st.push(node->val);

            // 如果当前节点的左子树为空
            // 并且当前节点的右子树也为空
            // 即当前节点为叶子节点
            // 同时当前路径下的节点值之和 value 与目标值 targetSum 相等
            // 说明找到了一条符合条件的路径
            if(node->left == NULL && node->right == NULL && value == targetSum){

                // 把这条路径添加到 path 中
                //以下代码是将路径转化成数组
                vector<int>v;
                stack<int>temp = st;
                while(!temp.empty()){
                    int ele = temp.top();
                    temp.pop();
                    v.insert(v.begin(), ele);
                }
                path.push_back(v);
            }

            // 继续递归的搜索当前节点 node 的左子树
            search(node->left,value,targetSum,st,path);

            // 继续递归的搜索当前节点 node 的右子树
            search(node->right,value,targetSum,st,path);

            // 搜索完当前节点的左右子树之后，当前节点已经完成了访问，需要返回到它的父节点
            // 所以 value 减去当前节点的值
            value -= node->val;

            // 栈也弹出当前的节点值
            st.pop();

    }
};

3、Python 代码

# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 路径总和 II（ LeetCode 113 ）: https://leetcode-cn.com/problems/path-sum-ii/
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:

        # 构建一个 value，用来计算当前路径下节点的总和
        value = 0

        # 构建一个 path，用来记录满足条件的路径
        path  = []

        # 构建一个栈，用来保存当前路径下的节点
        stk = []

        # 从根节点开始搜索
        self.search(root,value,targetSum,stk,path)

        # 返回满足条件的路径
        return path



    # node 为正在遍历的节点
    # value 为栈中各个节点值的总和
    # targetSum 为目标路径的和
    # stk 存储该路径上的所有节点
    # path 存储满足条件，即路径上的各个节点之和为 targetSum 的那些路径
    def search(self , node : TreeNode , value : int , targetSum: int , stk: [] , path: [] ) :

            # 如果节点为空，那么就不需要再访问下去了
            if not node :
                return

            # 将当前访问节点的值累加到 value 上
            value += node.val

            # 把当前的节点值添加到栈中，栈中保存的就是从根节点到当前节点的路径
            stk.append(node.val)

            # 如果当前节点的左子树为空
            # 并且当前节点的右子树也为空
            # 即当前节点为叶子节点
            # 同时当前路径下的节点值之和 value 与目标值 targetSum 相等
            # 说明找到了一条符合条件的路径
            if not node.left  and not  node.right and value == targetSum :

                # 把这条路径添加到 path 中
                path.append(list(stk))


            # 继续递归的搜索当前节点 node 的左子树
            self.search(node.left,value,targetSum,stk,path)

            # 继续递归的搜索当前节点 node 的右子树
            self.search(node.right,value,targetSum,stk,path)

            # 搜索完当前节点的左右子树之后，当前节点已经完成了访问，需要返回到它的父节点
            # 所以 value 减去当前节点的值
            value -= node.val

            # 栈也弹出当前的节点值
            stk.pop()

四、动画理解（没有声音）

程序员吴师兄算法训练营永久会员

收藏 海报 链接