将树节点的路径打印为列表

Question

我有点疯了

我的目标很简单。在二叉树中，指定一个节点并以列表形式返回该节点的路径。 有许多可用的实现

Here是最好和最严格的方法之一：

def path(root, k):
    if not root:
        return []
    if root.val == k:
        return [root.val]
    res = path(root.left, k)
    if res:
        return [root.val] + res
    res = path(root.right, k)
    if res:
        return [root.val] + res
    return []

出于纯粹的教育原因，我决定用一个helper函数重写它，在这个函数中我传递一个空列表并递归地向其中添加元素

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

    def path2Node2(self, root, node2):
        if not root:
            return None

        def _helper(root, node, paths):
            if not root:
                return []
            if root.val == node.val:
                paths.append(root.val)
                return paths
            return _helper(root.left, node, paths + [root.val])
            return _helper(root.right, node, paths + [root.val])


        return _helper(root, node2, [])


if __name__ == '__main__':
    l = TreeNode(10)
    l.left = TreeNode(8)
    l.right = TreeNode(2)
    l.left.left = TreeNode(3)
    l.left.right = TreeNode(5)
    l.right.left = TreeNode(4)
    print(l.path2Node2(l, l.left))

如果我通过根节点（print（l.path2Node2（l，l）），它就会工作

如果我传递左边的子项（print（l.path2Node2（l，l.left）），它就会工作

但如果我通过l.left.right或l.right.left，它将返回[]

在过去的几个小时里我都想不出来。我错过了什么

Answer 1

这是我自己问题的答案

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

    def path2Node2(self, root, node2):
        if not root:
            return []

        def _helper(root, node, paths):
            if not root:
                return []
            if root.val == node.val:
                paths.append(root.val)
                return paths
            l = _helper(root.left, node, paths + [root.val])
            r =  _helper(root.right, node, paths + [root.val])
            if l: return l
            if r: return r

        return _helper(root, node2, [])


if __name__ == '__main__':
    l = TreeNode(10)
    l.left = TreeNode(8)
    l.right = TreeNode(2)
    l.left.left = TreeNode(3)
    l.left.right = TreeNode(5)
    l.right.left = TreeNode(4)
    print(l.path2Node2(l, l.right))

我添加了两行：

if l: return l
if r: return r

但我仍然不明白我最初的方法有什么不同

Answer 2

看起来您正在解决今天的CodeSignal挑战。这是我的Python3解决方案。希望能有帮助

#
# Binary trees are already defined with this interface:
# class Tree(object):
#   def __init__(self, x):
#     self.value = x
#     self.left = None
#     self.right = None
def findCommonValues(t1, t2):
    def dfs(node:Tree, vals:list, comparison:dict=None):
        """Run a depth-first search on the tree by passing the root. If comparison is passed, then it
        is used to determine if we should add the value of node to the vals list. Otherwise, always
        add value to the vals list."""
        if not node:
            return
        if node.left:
            dfs(node.left, vals, comparison)
        if comparison is None or node.value in comparison:
            vals.append(node.value)
        if node.right:
            dfs(node.right, vals, comparison)

    # Create an empty list and use it to gather all the values from the first Tree
    vals = []
    dfs(t1, vals)
    # This line coverts my list to a dict, where each item in the list is a key, and the val is 
    # arbitrary (it will just be an incremented int here). This way, we can search for previous values
    # with constant run time.
    comparison = {k: v for v, k in enumerate(vals)}
    # Reset the list and process the 2nd Tree
    vals = []
    dfs(t2, vals, comparison)
    # Now the vals list has what we're looking for, thanks to line 17 in dfs
    return vals

对于那些在未来关注这一点的人来说，here是一个与CodeSignal挑战（以前是CodeFights）的链接