兩節點之間的祖先

Question

我有一個關於如何查找二叉搜索樹上兩個節點之間的最小公共祖先的問題。這是來自我的項目，我做了以下內容，但審閱者希望我實現高效的解決方案，而無需創建樹並添加節點。我的意思是我需要做什麼來修復我的代碼？

root = None 

Class Node: 
    #Constructor to create a new node 
    def __init__(self, data): 
     self.data = data 
     self.left = None 
     self.right = None 

    # Function to insert a new node at the beginning 
    def insert_right(node, new_data): 
     new_node = Node(new_data) 
     node.right = new_node 
     return new_node 

    # Function to insert a new node at the beginning 
    def insert_left(node, new_data): 
     new_node = Node(new_data) 
     node.left = new_node 
     return new_node  

    # Function to find least common ancestor 
    def lca(root, n1, n2): 

     # Base case 
     if root is None: 
      return None 

     # If both n1 and n2 are smaller than root, 
     # then LCA lies on left 
     if(root.data > n1 and root.data > n2): 
      return lca(root.left, n1, n2) 

     # if both n1 and n2 are greater than root, 
     # then LCA lies on right 
     if(root.data < n1 and root.data < n2): 
      return lca(root.right, n1, n2) 

     return root.data 

    def question4(the_matrix, the_root, n1, n2): 
     global root 
     root = Node(the_root) 
     root.left, root.right = None, None 
     node_value = 0 
     tmp_right, tmp_left = None, None 
     node_list = [] 
     for elem in the_matrix[the_root]: 
      if elem: 
       if(node_value>the_root): 
        node_list.append(push_right(root, node_value)) 
       else: 
        node_list.append(push_left(root, node_value)) 
      node_value += 1 

     tmp_node = node_list.pop(0) 
     while tmp_node != None: 
      node_value = 0 
      for elem in the_matrix[tmp_node.data]: 
       if elem: 
        if(node_value>tmp_node.data): 
         node_list.append(push_right(tmp_node, node_value)) 
        else: 
         node_list.append(push_left(tmp_node, node_value)) 
       node_value += 1 
      if node_list == []: 
       break 
      else: 
       tmp_node = node_list.pop(0) 

     return lca(root, n1, n2) 

def main(): 
    global root  
    print question4([[0, 0, 0, 0, 0], 
        [1, 0, 1, 0, 0], 
        [0, 0, 0, 0, 0], 
        [0, 1, 0, 0, 1], 
        [0, 0, 0, 0, 0]],3, 1, 2) 

if __name__ == '__main__': 
    main() 

Answer 1

而是對你定義的樹結構實現lca的，審稿人要你直接使用矩陣表示找到LCA。

基本上，不要使用Node類，只是使用矩陣行來理解節點關係。