二叉树的Python递归路径查找器

Question

我试图用python写一个递归函数，给定一个二叉树，一个节点返回一个包含节点方向的字符串。我已经接近了，但是我的最终返回语句给了我路径和节点(我不需要节点)即LRLR4。

这是我到目前为止的代码：

class Tree:
    def __init__(self):
        self.root = None
        self.left = None
        self.right = None

    def join(item: object, left: Tree, right: Tree):
        tree = Tree()
        tree.root = item
        tree.left = left
        tree.right = right
        return tree

def path(tree: Tree, node: str, out: str=""):
    if not tree:
        return ""
    if tree.root == node:
        return tree.root
    res = path(tree.left, node)
    if res:
        return "L" + res    
    res = path(tree.right, node)
    if res:
        return "R" + res

有没有一种方法可以在不使用字符串输出末尾的节点的情况下实现这一点？

编辑：添加了所有实际代码，并且有问题的树包含每个节点的单个字母字符串。

Answer 1

要写入路径 -

def path(tree, target):
  if not tree:
    return ""
  elif target < tree.root:
    return "L" + path(tree.left, target)
  elif target > tree.root:
    return "R" + path(tree.right, target)
  else:
    return ""  # tree.root equal to target; don't return node

不过，我们可以对您的Tree类进行更多改进。查看加入中的这些作业？

def join(item: object, left: Tree, right: Tree):
    tree = Tree()
    tree.root = item
    tree.left = left
    tree.right = right
    return tree

如果Tree构造函数将这些值作为参数会更好-

class Tree:
    def __init__(self, root, left = None, right = None):
        self.root = root
        self.left = left
        self.right = right

    def join(item, left, right):
      return Tree(item, left, right) # pass as arguments

现在加入函数是多余的，可以删除-

class Tree:
    def __init__(self, root, left = None, right = None):
        self.root = root
        self.left = left
        self.right = right

    # no more need for `join`

鉴于我的树 -

#         g
#       /   \
#      /     \
#     d       m
#    / \     / \
#   b   f   j   q 
#  /         \
# a           k      

mytree = \
  Tree("g",
    Tree("d", Tree("b", Tree("a")), Tree("f")),
    Tree("m", Tree("j", None, Tree("k")), Tree("q"))
  )

print(path(mytree, "f")) # LR
print(path(mytree, "k")) # RLR
print(path(mytree, "q")) # RRR