在解決二進制搜索樹中的節點問題時遇到問題

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