python - 求解二叉搜索树中的下一个中序节点时遇到问题

Question

我被这个问题困扰了。我失败的边缘情况是给定节点(自身)是树中最大的节点。我将不胜感激任何解决问题的提示。

我提出的情况是，当节点的右侧为“无”时，那么我知道解决方案将是祖 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()

Answer 1

如果您重写 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()