在解决二进制搜索树中的节点问题时遇到问题

Question

我被困在这个问题上。我失败的边缘情况是给定节点（self）是树中最大的节点。我将不胜感激解决问题的任何提示。

我想到的情况是，当节点的权利是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): 

如果自为1，返回3

如果自为3，返回4

如果自为4，则返回5

如果自为9，返回无

我的解决方案：

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()