我被这个问题困扰了。我失败的边缘情况是给定节点(自身)是树中最大的节点。我将不胜感激任何解决问题的提示。
我提出的情况是,当节点的右侧为“无”时,那么我知道解决方案将是祖 parent 或“无”。
另一种情况是 right 不为 None 时。在这种情况下,我调用右子节点并找到最左边的节点,因为它将是大于起始自节点的最小节点。
给定一个 BSTNode 对象,返回下一个有序节点。
class BSTNode:
def __init__(self, left, right, parent):
self.left = left # BSTNode
self.right = right # BSTNode
self.parent = parent # BSTNode
def nextInorderNode(self):
如果 self 为 1,则返回 3
如果 self 为 3,则返回 4
如果 self 是 4,则返回 5
如果 self 是 9,则返回 None
我的解决方案:
class BSTNode:
def __init__(self, left, right, parent):
self.left = left # BSTNode
self.right = right # BSTNode
self.parent = parent # BSTNode
def find_left_most(self):
if (self == None):
return self
next = self
while (next != None):
if (next.left == None):
return next
next = next.left
def nextInorderNode(self):
if self.right == None:
parent = self.parent
if (parent.left == self):
return parent
else:
curr_node = parent.right
grand_parent = parent.parent
return grand_parent
else:
child = self.right
return child.find_left_most()
最佳答案
如果您重写 nextInorderNode
来遍历树,直到找到 self
位于左侧的节点,我认为这会给您想要的结果:
def nextInorderNode(self):
if self.right is None:
curr_node = self
parent = curr_node.parent
while parent and parent.left != curr_node:
curr_node = parent
parent = curr_node.parent
return parent
child = self.right
return child.find_left_most()
关于python - 求解二叉搜索树中的下一个中序节点时遇到问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46718851/