我试图用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
有没有一种方法可以在不使用字符串输出末尾的节点的情况下实现这一点?
编辑:添加了所有实际代码,并且有问题的树包含每个节点的单个字母字符串。
要写入路径
-
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。 如果树是二叉搜索: