이 진 트 리 두 결점 의 최저 공공 조상 결점 (1)

제목.
두 갈래 나무 결점 의 정 의 는 다음 과 같다.

struct node {
    int data;
    struct node* left;
    struct node* right;
};

이 진 트 리 의 두 결점 을 정 해 두 결점 의 최소 공공 조상 결점 (LCA) 을 출력 한다.이 이 진 트 리 가 꼭 이 진 트 리 는 아 닙 니 다.
예 를 들 어 주어진 이 진 트 리 는 다음 과 같이 결점 1 과 5 의 최저 공공 조상 결점 이 5 이 고 결점 4 와 5 의 최저 공공 조상 결점 이 5 라 는 것 을 알 수 있다.

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

 
해법
1) 위 에서 아래로 내 려 가 는 방법
우 리 는 뿌리 결점 에서 출발 하여 현재 결점 의 좌우 자나무 가 이 두 결점 을 포함 하고 있 는 지 판단 할 수 있다.왼쪽 나무 에 두 개의 결점 이 포함 되 어 있다 면, 그들의 최저 공공 조상 결점 도 반드시 왼쪽 나무 에 있 을 것 이다.오른쪽 나무 에 두 개의 결점 이 포함 되 어 있다 면, 그들의 최저 공공 조상 결점 도 반드시 오른쪽 나무 에 있 을 것 이다.만약 에 하나의 결점 이 왼쪽 나무 에 있 고 다른 결점 이 오른쪽 나무 에 있다 면 현재 의 결점 은 그들의 가장 낮은 공공 조상 결점 이다.이 사고방식 에 따라 코드 를 다음 과 같이 쓰 십시오. 여기에 p 와 q 가 이 진 트 리 의 결점 이 라 고 가정 되 어 있 음 을 주의 하 십시오.

/*                  */
struct node* LCA(struct node *root, struct node *p, struct node *q) 
{
    if (hasNode(root->left, p) && hasNode(root->left, q)) //p q              
        return LCA(root->left, p, q);
    if (hasNode(root->right, p) && hasNode(root->right, q)) //p q      
        return LCA(root->right, p, q);
    return root; //p q      ，       ，    root
}

/*  root          p*/
bool hasNode(struct node* root, struct node* p)
{
    if (!root) return false;
    if (root == p)
        return true;
    return hasNode(root->left, p) ||  hasNode(root->right, p);
}

우 리 는 모든 노드 에 hasNode 함 수 를 호출 했 기 때문에 이 함 수 는 이 진 트 리 를 옮 겨 다 니 는 것 과 유사 하고 복잡 도 는 O (N) 이기 때문에 전체적인 시간 복잡 도 는 O (N ^ 2) 이 므 로 더 좋 은 방법 을 찾 고 싶 습 니 다.
 
2) 밑 에서 위로 올 라 가 는 방법
위 에서 아래로 내 려 가 는 방법 은 결점 을 반복 해서 옮 겨 다 녀 야 하기 때문에 아래 에서 위로 올 라 가 는 방법 을 사용 하면 이런 상황 을 피 할 수 있다.
아래 에서 위로 결점 을 옮 겨 다 니 며 결점 이 p 또는 q 와 같 으 면 부모 결점 에 전달 합 니 다.부모 노드 는 좌우 하위 트 리 에 하나의 노드 가 포함 되 어 있 는 지 판단 합 니 다. 만약 그렇다면 부모 노드 는 반드시 이 두 노드 p 와 q 의 LCA 로 부모 노드 를 루트 로 전달 합 니 다.만약 그렇지 않다 면, 우 리 는 결점 p 또는 q 를 포함 하 는 하위 결점 이나 NULL 을 위로 전달 합 니 다.이 방법의 시간 복잡 도 는 O (N) 이다.

typedef struct node Node;
Node *LCA(Node *root, Node *p, Node *q) {
  if (!root) return NULL;
  if (root == p || root == q) return root;
  Node *L = LCA(root->left, p, q);
  Node *R = LCA(root->right, p, q);
  if (L && R) return root;  //   p q         
  return L ? L : R;  //p q      ，  p q     
}

3) 공통 경로 법
또 하나의 방법 은 뿌리 결점 에서 결점 p 와 q 까지 의 경 로 를 순서대로 얻어 그들의 경로 중의 마지막 공공 결점 인 LCA 를 찾아내 는 것 이다.이 알고리즘 은 하 해도 선생 의 블 로그 에 상세 하 게 묘사 되 어 있 으 니, 여기 서 는 군말 하지 않 겠 다. 상세 한 것 은 다음 과 같다.http://zhedahht.blog.163.com/blog/static/25411174201081263815813/이 방법의 복잡 도도 O (N) 이지 만 추가 적 인 공간 저장 경로 가 필요 하 다. 물론 두 번 째 방법 중 귀속 도 창고 공간 이 필요 하지만 전체적으로 보면 두 번 째 방법 은 간결 하지만 이해 하기 어렵다.공공 경로 의 법칙 은 더욱 이해 하기 쉽다.