두 노드 사이의 조상

Question

이진 탐색 트리에서 두 노드 사이에 최소한의 공통 조상을 찾는 방법에 대한 질문이 있습니다. 이것은 내 프로젝트에서 다음과 같았지만 리뷰 작성자는 트리를 만들고 노드를 추가하지 않고도 효율적인 솔루션을 구현하기를 원합니다. 내 코드를 수정하려면 어떻게해야합니까? 대신 당신이 정의하고있는 트리 구조에 lca을 구현

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를 찾기 위해 직접 행렬 표현을 사용하고 싶어.

기본적으로 Node 클래스를 사용하지 말고 매트릭스 행을 사용하여 노드 관계를 이해하십시오.