如何获得一个非常大的二叉树中节点的级别

Question

我正在做一个编码挑战，在这个挑战中，我要在元组的二进制树中找到一个节点的级别(如果存在的话(。我的解决方案效率不高，只适用于低级别节点。如何优化代码以适用于非常大的级别？

元组的生成模式在Node类中。

例如，解决方案("4"，"7"(将返回4，而解决方案("2"，"1"(将返回1

from itertools import product
class Node:
def __init__(self,data):
self.data = data
self.left = (self.data[0] + self.data[1], self.data[1])
self.right = (self.data[0], self.data[0] + self.data[1])
def lefts(self):
self.data = self.left
def rights(self):
self.data = self.right
def getter(self):
return self.data
def solution(x,y):
tup = (int(x),int(y))
a = ['left', 'right']
directions = list(product(a,repeat=int(max(tup))))
for direction in directions:
node = Node((1,1))
count = 0
for lor in direction:
if node.getter() == tup:
return count
if lor == 'left':
node.lefts()
node = Node(node.getter())
else:
node.rights()
node = Node(node.getter())
count += 1

return 'impossible'

Answer 1

对于这个问题，实际创建一个二叉树是过分的。

更重要的是，最好从相反的方向来看待问题，即从给定的(x，y("开始"；节点"；并确定它的父对象是什么，然后重复该步骤以走向根。

这更有趣，因为一个节点只有一个父节点，因此不需要考虑任何替代方案。如果这条路径指向节点(1，1(，那么我们找到了解决方案。然而，如果路径指向一个元组，该元组的成员不是严格正的，那么我们可以得出结论，没有解决方案。。。显然，该节点是一个不同树的成员。

"；公式"；得到(x，y(的父节点是

• (x，y-x(当y>x
• (x-y，y(否则

根据这些观察结果，程序非常简单：

def solution(x, y):
count = 0
while x > 1 and y > 1:
if x > y:
x -= y
else:
y -= x
count += 1
return count + abs(x - y) if min(x, y) == 1 else "impossible"