2つのノード間の祖先

Question

バイナリ検索ツリー上の2つのノード間で最小の共通祖先を見つける方法に関する質問があります。これは私のプロジェクトからですが、私は次のようにしましたが、査読者はツリーを作成せずノードを追加することなく効率的なソリューションを実装したいと考えています。コードを修正するために何をする必要があるのですか？

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クラスは使用しないでください。行列の行を使用してノードの関係を理解し​​てください。