当前位置: 首页 > 知识库问答 >
问题:

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

何建中
2023-03-14

我试图用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

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

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

共有1个答案

瞿博学
2023-03-14

要写入路径 -

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
 类似资料:
  • 我有一个<code>BinarySearchTree</code>,里面有Instance bankaccount的对象,这是我创建的一个类,所以基本上它只是一个二进制搜索树,我编写了一个方法,它将获取树并对其进行平衡,因为某些原因,它在平衡之前准确地打印出树: 现在,首先我有方法,它接受一个列表和一个并通过按顺序检查树数据来创建树数据的,因此它是一个排序数组。然后使用另一种方法以平衡的方式创建树

  • 我试图递归地在二叉树中找到最小值(不是二叉查找树)。让我困惑的是基本情况。如果TreeNode t为空,返回什么?因为我将使用返回的值将其与当前的最小值进行比较(我认为),我相信我返回的内容很重要。

  • 我创造了这个二叉查找树。我使用循环和递归编写了两种形式的插入方法。递归代码虽然看起来是正确的,但并不工作,我想不出问题是什么。当我使用insertRecursion方法创建树时,leftChild和rightChild总是为null。 }

  • 我有TreeNode类——非二叉树(

  • 我正在努力解决一个问题二叉树的最大深度-LeetCode 这个问题是在leetcode教程中作为尾递归练习给出的。尾递归-LeetCode 给定一棵二叉树,求其最大深度。 最大深度是从根节点到最远叶节点的最长路径上的节点数。 注意:叶子是没有子节点的节点。 例子: 给定二叉树, 返回其深度=3。 一种标准的解决方案,从级别的定义来看待问题 然而,它不是尾部递归 尾递归是递归,其中递归调用是递归函数

  • 我坚持使用递归函数来查找二叉树中节点的深度,更具体地说,是在else条件中: 如果树是二叉搜索树,知道左子值总是低于父值,右子值总是高于父值,我可以添加一个If条件,这样如果节点x值低于根,我总是返回根- 当查看函数时,假设节点总是存在的,节点x永远不是根,并且在开始时传递的深度总是0。 如果树是二叉搜索: