递归 DFS 函数不将每个根返回到叶路径

Question

我目前正在尝试制作一个包含二叉树中所有根到叶路径的列表列表。当我尝试写出路径列表和所有递归调用的结果时，我似乎无法弄清楚错误出在哪里。我想到了在撞到一片叶子后从每条单独的路径中弹出的想法，但这也产生了奇怪的结果。我还包括树节点的定义，它是输入的格式。

当前输入：[1,2,3,null,5]（1为根，2和3为1的child任，5为2的右child）预期输出：[[1,2,3],[1,3]] 当前输出：[[1,2,5,3],[1,2,5,3]]

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



def binaryTreePaths(self, root: Optional[TreeNode]):
    if not root:
        return
    paths = []
    def traverse(root,path,paths):
        if not root:
            return []
        path.append(root.val)
        if not root.left and not root.right:
            paths.append(path)
            
        traverse(root.left,path,paths)
        traverse(root.right,path,paths)
        
        
    traverse(root,[],paths)
    return paths

Answer 1

如果我没记错的话，你在做这个LC题。 https://leetcode.com/problems/binary-tree-paths/

我已经在LC上解决了这个问题，所以粘贴修改后的版本并附上评论。

def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
    # for empty root, return empty array
    if not root:
        return []

    # variable to hold all paths
    paths = []
    def traverse(root,path,paths):

        if not root:
            return

        # if root(node) is not empty, this node value will need to be added in current path
        path.append(root.val)

        # if the above node is leaf node,
        # we have to make a copy of path (since list are mutable)
        # and then pop the element of this current path as we back track
        if not root.left and not root.right:
            paths.append(path[:])
            path.pop()
            return 

        # if above node was not leaf node, then travese right and left
        traverse(root.left,path,paths)
        traverse(root.right,path,paths)

        # once traversed, we backtrack by popping
        path.pop()

    traverse(root,[],paths)
    return paths

递归 DFS 函数不将每个根返回到叶路径

Recursive DFS Function not returning every Root to Leaf Path

python

binary-tree

depth-first-search