0236-이차나무의 최근 공공조상

두 갈래 나무의 최근 공공 조상

시나리오 1

두 갈래 트리에서 p와 q를 검색한 다음에 경로에서 마지막 같은 노드가 아버지 노드인 것을 찾으면 귀속으로 실현할 수 있다. 귀속 함수에서 우리는 먼저 현재 결점이 비어 있는지, 비어 있으면 비어 있는지, p 또는 q 중 임의의 노드인 경우 현재 결점을 직접 되돌릴 수 있다.그렇지 않으면 좌우 결점에 대해 각각 귀속 함수를 호출한다. 이 문제는 p와 q가 반드시 두 갈래 나무에 존재하도록 제한하기 때문에 현재 결점이 p나 q와 같지 않으면 p와 q는 각각 좌우 나무에 있거나 왼쪽 나무에 있거나 오른쪽 나무에 있으면 우리는 각각 토론한다.
만약에 p와 q가 각각 좌우 서브 트리에 위치하거나 좌우 서브 결점에 대해 귀속 함수를 호출하면 각각 p와 q 결점의 위치를 되돌려준다. 현재 결점은 바로 p와 q의 최소 공통 부결점이다. 현재 결점을 직접 되돌려주면 된다. 이것이 바로 문제의 예1의 상황이다.
만약에 p와 q가 동시에 왼쪽 트리에 위치한다면 여기에는 두 가지 상황이 있다. 하나는 left가 p와 q에서 비교적 높은 위치를 되돌려주고 right는 비어 있기 때문에 우리는 최종적으로 비어 있지 않은 left를 되돌려주면 된다. 이것이 바로 문제의 예2의 상황이다.또 다른 상황은 p와 q의 최소 부결점으로 되돌아오는 것이다. 즉, 현재 결점의 왼쪽 트리 중의 어떤 결점이야말로 p와 q의 최소 부결점으로 되돌아오는 것이다.
만약에 p와 q가 동시에 오른쪽 트리에 위치한다면 마찬가지로 여기에는 두 가지 상황이 있다. 하나는 right가 p와 q에서 비교적 높은 위치를 되돌려주고 left는 비어 있기 때문에 우리는 최종적으로 비어 있지 않은 right를 되돌려주면 된다. 또 하나는 p와 q의 가장 작은 부결점을 되돌려준다. 즉, 현재 결점의 오른쪽 부결점이 p와 q의 가장 작은 부결점이다.

C++ - 소스 코드

#include 
//#include 
//#include 

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        
        if (!root || p == root || q == root) {
            
            return root;
        }
        
        TreeNode *left = lowestCommonAncestor(root->left, p, q);
        TreeNode *right = lowestCommonAncestor(root->right, p, q);
        
        if (left && right) {
            
            return root;
        }
        
        if (left) {
            
            return left;
        }
        else {
            
            return right;
        }
    }
};

방안 2

만약에 현재 결점이 비어 있지 않고 p도 q도 아니라면 위의 분석에 의하면 p와 q의 위치는 세 가지 상황이 있다. p와 q는 각각 좌우 나무에 있거나 왼쪽 나무에 있거나 오른쪽 나무에 있다.우리가 최적화해야 할 상황은 p와 q가 동시에 왼쪽 트리나 오른쪽 트리에 있고 되돌아오는 결점은 p나 q가 아니다. 그러면 p와 q의 최소 부결점이다. 이미 구해냈기 때문에 더 이상 오른쪽 결점에 귀속 함수를 호출할 필요가 없다

C++ - 소스 코드

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        
        if (!root || p == root || q == root) {
            
            return root;
        }
        
        TreeNode *left = lowestCommonAncestor(root->left, p, q);
        if (left && left != p && left != q) {
            
            return left;
        }
        TreeNode *right = lowestCommonAncestor(root->right, p, q);
        
        if (left && right) {
            
            return root;
        }
        
        if (left) {
            
            return left;
        }
        else {
            
            return right;
        }
    }
};

Grandyang 참조