Leetcode - 236. Lowest Common Ancestor of a Binary Tree

문제

binary tree에서 두 노드의 가장 가까운 공통 부모를 찾아라.

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.

해결 아이디어

재귀함수는 자식노드에 q, p노드가 존재하면 해당 노드를 리턴, 아니라면 NULL리턴.
left, right에 노드가 NULL인지 아닌지로 현재 노드가 LCA인지 아닌지 판단 가능.

해결

재귀 호출 이후 논리전개가 이해하기조금 어려웠음.

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // check the node is null or not null 
        if (root == NULL)
            return root;
        if (root == p || root == q)
            return root;
        TreeNode *left = lowestCommonAncestor(root->left, p, q);
        TreeNode *right = lowestCommonAncestor(root->right, p, q);
        
        if (left && right)
            return root;
        if (!left && right)
            return right;
        if (left && !right)
            return left;
        return NULL; // if both are null
    }
};

아래와 같이 하는것도 가능. 위 아래가 동일한 논리구조인지 이해필요!

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // check the node is null or not null 
        if (root == NULL)
            return root;
        if (root == p || root == q)
            return root;
        TreeNode *left = lowestCommonAncestor(root->left, p, q);
        TreeNode *right = lowestCommonAncestor(root->right, p, q);
        if (left == NULL) // if left is NULL, return right whether it is null or not.
            return right; // just return right for possible not null
        else if (right == NULL)
            return left; 
        else // if left and right are not NULL, it means the answer.
            return root;
    }
};