时间戳

首页 > 解决方案 > Path Sum 的递归实现问题

algorithm - Path Sum 的递归实现问题

问题描述

我正在尝试从 leetcode(#113 Path Sums II) 中回答这个问题。

给定一棵二叉树和一个总和，找到所有从根到叶的路径，其中每个路径的总和等于给定的目标总和。

我的做法：

这个问题似乎适合递归。我从树的最顶端开始。每次遇到非叶节点时，我都会进一步递归到树中，同时跟踪current_path我采取的和我的current_sum. 如果我遇到叶节点，我会检查 mycurrent_sum是否等于target. 如果是，我将该路径添加到我想要返回的路径列表中。否则，我们会探索其他路径。

def pathSum(self, root: TreeNode, target: int) -> List[List[int]]:
    paths = [] #variable we return
    
    def dfs(node, current_sum = 0, current_path = []):
        if not node:
            return False #Edge case
        
        # Adding my current place
        current_path.append(node.val)
        current_sum += node.val
        
        if not node.left and not node.right: # Is this a leaf node?
            if current_sum == target: #Is the sum == target
                paths.append(current_path) #Add the current path
                
        else: #keep recursing since we are not at the leaf
            dfs(node.left, current_sum, current_path) 
            dfs(node.right, current_sum, current_path)
            
    dfs(root,0,[])
    return paths

但是，由于某种原因，我的 current_path 变量就像一个全局变量......在我的脑海中，每次dfs()调用我们都会创建一个单独的current_path变量，该变量会传递给dfs()我们稍后调用的函数。但是，当我实际运行代码时，current_path会跟踪我访问过的所有节点。

极其奇怪的是，即使current_path跟踪其他递归调用中发生的事情，current_sum也不会。我从来没有遇到过其他递归实现的这个问题......

任何指针将不胜感激:)

标签： algorithmrecursiontreedepth-first-search

解决方案

我的猜测是，您在没有任何条件语句的情况下node.val在此处附加了任何内容：current_path

current_path.append(node.val)

这可能会导致算法错误。

在 Python 中，这将通过，与 DFS 类似：

class Solution:
    def pathSum(self, root, target):
        def depth_first_search(node, target, path, res):
            if not (node.left or node.right) and target == node.val:
                path.append(node.val)
                res.append(path)

            if node.left:
                depth_first_search(node.left, target - node.val, path + [node.val], res)

            if node.right:
                depth_first_search(node.right, target - node.val, path + [node.val], res)

        res = []
        if not root:
            return res

        depth_first_search(root, target, [], res)
        return res

同样在 C++ 中：

// The following block might trivially improve the exec time;
// Can be removed;
static const auto __optimize__ = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
    return 0;
}();


#include <vector>

const static struct Solution {
        const static  std::vector<std::vector<int>> pathSum(
            const TreeNode* root, 
            const int sum
            ) {
            std::vector<std::vector<int>> paths;
            std::vector<int> path;

            depthFirstSearch(root, sum, path, paths);

            return paths;
        }

    private:
        const static void depthFirstSearch(
            const TreeNode* node,
            const int sum,
            std::vector<int>& path,
            std::vector<std::vector<int>>& paths
        ) {
            if (!node) {
                return;
            }

            path.emplace_back(node->val);

            if (!node->left && !node->right && sum == node->val) {
                paths.emplace_back(path);
            }

            depthFirstSearch(node->left, sum - node->val, path, paths);
            depthFirstSearch(node->right, sum - node->val, path, paths);
            path.pop_back();
        }
};

在 Java 中，我们会使用两个 LinkedList：

public final class Solution {
    public static final List<List<Integer>> pathSum(
        final TreeNode root, 
        final int sum
    ) {
        List<List<Integer>> res = new LinkedList<>();
        List<Integer> tempRes = new LinkedList<>();
        pathSum(root, sum, tempRes, res);
        return res;
    }

    private static final void pathSum(
        final TreeNode node, 
        final int sum, 
        final List<Integer> tempRes, 
        final List<List<Integer>> res
    ) {
        if (node == null)
            return;

        tempRes.add(new Integer(node.val));

        if (node.left == null && node.right == null && sum == node.val) {
            res.add(new LinkedList(tempRes));
            tempRes.remove(tempRes.size() - 1);
            return;

        } else {
            pathSum(node.left, sum - node.val, tempRes, res);
            pathSum(node.right, sum - node.val, tempRes, res);
        }

        tempRes.remove(tempRes.size() - 1);
    }
}

参考

  • 有关更多详细信息，请参阅讨论板，您可以在其中找到大量解释清楚且公认的解决方案，这些解决方案具有多种语言，包括低复杂度算法和渐近运行时/内存分析1、2。

推荐阅读