4 0 2
0 1
0 3
2 3
0
3
我正在尝试找到解决上述问题的有效方法。
给定输入第一行是:二叉树中的节点数=4
,root=0
,depths=2
边或边上的节点没有以任何特定顺序给出,但连接节点到左子节点的边出现在输入中。
最后两行求0和3的位置,输出为
1 2
3 1
树可以有超过百万个节点并使用构建树
我找不到如何以可以找到节点坐标的方式表示树
更新代码
class node:
def __init__(self, x):
self.x=4
self.l=2
self.r=0
self.id=id
def recurse(node,id, depth = -1, position=-1, max_depth=-1):
depth=depth+1
current_depth=depth
max_depth=max(max_depth,current_depth)
matchl=False
matchr=False
if node.l :
(depthl,position,max_depth,matchl)=node.recurse(node.l,id,current_depth,position,max_depth)
positionl = position
position = position + 1
current_position=position
if node.r:
(depth,position,max_depth,matchr)=node.recurse(node.r,id,current_depth,position,max_depth)
if matchl:
return (depthl,positionl,max_depth,True)
if node.x==id:
return (current_depth,current_position,max_depth,True)
return (depth,position,max_depth,matchr)
n2=node(2)
n3=node(3)
n1=node(1)
n0=node(0)
n0.l=n1
n0.r=n3
n3.l=n2
(depth,position,max_depth,match)=node.recurse(n0,3)
if match:
answer = (position, max_depth - depth )
最佳答案
给出问题的方式假设没有两个节点可以共享一列,并且首先填充左节点,因为如果您以正确的顺序遍历树(左叶,节点,右叶):
以下代码未经测试,但应该能让您对算法有所了解:
def recurse( node, id, depth = -1, position=-1, max_depth=-1):
depth=depth+1
current_depth=depth
max_depth=max(max_depth,current_depth)
matchl=False
matchr=False
if node.l :
(depthl,position,max_depth,matchl)=recurse(node.l,id,current_depth,position,max_depth)
positionl = position
position = position + 1
current_position=position
if node.r:
(depth,position,max_depth,matchr)=recurse(node.r,id,current_depth,position,max_depth)
if matchl:
return (depthl,positionl,max_depth,True)
if node.x==id:
return (current_depth,current_position,max_depth,True)
return (depth,position,max_depth,matchr)
用法
(depth,position,match, max_depth) = recurse(root_node,target_id)
例子:
n2=node(2)
n3=node(3)
n1=node(1)
n0=node(0)
n0.l=n1
n0.r=n3
n3.l=n2
(depth,position,max_depth,match)=recurse(n0,3)
if match:
answer = (position, max_depth - depth )
关于python - 如何找到二叉树中节点的位置?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36164019/