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

Question

我正在尝试在 python 中编写一个递归函数，给定一个二叉树和一个节点 returns 一个包含节点方向的字符串。我已经接近了，但我最后的 return 语句给了我路径加上节点（我不需要节点）即 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

写path-

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 class 进行更多改进。在 join?

中查看这些作业

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

现在 join 功能是多余的，可以删除 -

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

    # no more need for `join`

给定 mytree -

#         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

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

Python recursive path finder for binary tree

python

tree

recursion

binary-tree

python-3.x