[leetcode 236] Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

 

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 Output: 3 Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 Output: 5 Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [1,2], p = 1, q = 2 Output: 1

 

Constraints:

• The number of nodes in the tree is in the range [2, 105].
• -109 <= Node.val <= 109
• All Node.val are unique.
• p != q
• p and q will exist in the tree.

문제 풀이:

- 최소 공통조상 찾기

- 어렵다...재귀를 이용한다.

- 조건에서 p와 q가 무조건 트리에 있을 것이라고 했기 때문에 경우의 수는 두가지로 나뉜다.

1) 왼쪽, 오른쪽에 각각 하나씩 있는 경우 2) 한 노드가 다른 하나의 부모 노드인 경우

1)의 경우 각 서브트리의 루트노드를 반환하면 공통 조상이다.

2)의 경우 한 노드만 반환

 

p와 q를 찾는 과정:

 

if(root == nullptr) return nullptr; //없으면 return null

if(root->val == p->val || root->val == q->val){
            return root; //있으면 해당 노드 반환
}

 

p와 q의 존재여부를 파악한다.

 

TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
        

left는 왼쪽 서브트리에서, right는 오른쪽 서브트리에서 p와 q를 찾는다.

 

만약 양쪽에서 발견된다면 출발한 root가 공통 조상이다.

 if(left && right) return root;

 

하나가 다른 하나의 부모노드라면 먼저 발견된 노드가 부모노드일 것이다...따라서 발견된 하나만 리턴하면 된다.

return left? left: right;

 

시간복잡도는 모든 노드를 탐방하므로 O(N)이다.

공간복잡도는 최악의 경우 트리의 높이와 노드수가 같아진다.(오른쪽 서브트리로만 연결) 따라서 O(H)

/**
 * Definition for a binary tree node.
 * 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==nullptr){
            return root;
        }
        
        if(root->val == p->val || root->val == q->val){
            return root;
        }
        
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        
        if(left && right){
            return root;
        }
        
        return (left)? left:right;
    }
};