최근 공공 조상 (LCA) 문제 노트

최근 공공 조상 (전재)
1. 폭력 적 인 대우    이 진 트 리 찾기: 노드 u, v 의 최근 공공 조상 찾기 순서
    1. 현재 의 결점 t 가 결점 u, v 보다 크 면 u, v 는 모두 t 의 왼쪽 에 있 기 때문에 그들의 공동 조상 은 반드시 t 의 왼쪽 나무 에 있다.
         그래서 t 의 왼쪽 트 리 에서 계속 찾 습 니 다.
    2. 현재 의 결점 t 가 결점 u, v 보다 작 으 면 u, v 가 모두 t 의 오른쪽 에 있다 는 것 을 의미한다. 그래서 그들의 공동 조상 은 반드시 t 의 오른쪽 나무 에 있다.
         그래서 t 의 오른쪽 트 리 에서 계속 찾 습 니 다.
   3. 현재 결산 점 t 만족 u
   4. u 가 v 의 조상 이 라면 u 의 아버지 결점 으로 돌아 갑 니 다. 마찬가지 로 v 가 u 의 조상 이 라면 v 의 아버지 결점 으로 돌아 갑 니 다.
예시:

public int query(Node t, Node u, Node v) {    
    int left = u.value;    
    int right = v.value;    
  
    //      ，          ，  ，    
    if (left > right) {    
        int temp = left;    
        left = right;    
        right = temp;    
    }    
  
    while (true) {    
        //  t  u、v， t         
        if (t.value < left) {    
            t = t.right;    
  
        //  t  u、v， t         
        } else if (t.value > right) {    
            t = t.left;    
        } else {    
            return t.value;    
        }    
    }    
} 

2. 보통 이 진 트 리
            만약 모든 결점 에 하나의 지침 이 그의 아버지 결점 을 가리 키 고 있다 면 우 리 는 어떤 결점 에서 출발 하여 나무 뿌리 결점 에 도착 하 는 단 방향 체인 시 계 를 얻 을 수 있다.그래서 이 문 제 는 두 개의 단 방향 링크 의 첫 번 째 공공 노드 로 바 뀌 었 다.루트 노드 를 제시 하면 LCA 문 제 는 재 귀적 으로 빠르게 해결 할 수 있다.그리고 나무 에 관 한 문 제 는 보통 재 귀적 으로 바 꿀 수 있 습 니 다 (트 리 는 원래 재 귀적 설명 이기 때 문 입 니 다). 참고 코드 는 다음 과 같 습 니 다.
        node getLCA(node root , node  node1, node node2)
 {
if(root==null) return null;
        if(root==node1 || root==node2) return root;
node left=getLCA(root.left, node1,node2);
        node right=getLCA(root.right , node1,node2);
        if(left != null && right != null)  
  
 
return
root;  
else
if
(left != null)  

    return left;  
    else if (right != null)  
        return right;  
    else   
        return null;  

} 

일반적인 이 진 트 리 든 이 진 트 리 를 찾 든 위의 해법 은 N 차 조회 가 필요 하면 전체적인 복잡 도가 N 배 확대 되 기 때문에 이런 폭력 해법 은 한 번 의 조회 에 만 적합 하고 여러 번 의 조회 에 적합 하지 않다 는 단점 이 있다.
뒤의 링크 는 더 많은 내용 이 있 습 니 다!
다음으로 전송:https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/03.03.md