[LeetCode] 236. Lowest Common Ancestor of a Binary Tree - 깊이우선탐색(DFS) JAVA

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/

코드설명

깊이우선탐색(DFS)을 활용합니다.

 

아래 정답코드1의 경우, 직접 모든 케이스를 명시하여 처리합니다. 비교적 쉬운 방식입니다.

 

정답코드2의 경우, root가 NULL이냐 아니냐에 따라 p인지 q인지 판단합니다.

또한, 만약 왼쪽 트리에서 NULL이 아니고, 오른쪽 트리에서 NULL이 반환된다면, 왼쪽트리가 반드시 LCA임을 알 수 있습니다. 왼쪽 자식 트리가 NULL이 아닌데, P 혹은 Q인데, 오른쪽 자식트리가 NULL이라면, 당연히 LCA입니다.

LCA에서의 트리 성질을 이해한다면 풀이가 가능한 방식입니다.

코드

정답코드1입니다.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    TreeNode P, Q, Root;
    TreeNode answer;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Root = root; P = p; Q = q;
        DFS(root);
        return answer;
    }

    boolean DFS(TreeNode root){
        boolean isCenterDescendant = false, isLeftDescendant = false, isRightDescendant = false;
        if(root == P || root == Q){
            isCenterDescendant = true;
        }
        if(root.left != null){
            isLeftDescendant |= DFS(root.left);
        }
        if(root.right != null){
            isRightDescendant |= DFS(root.right);
        }
        if( (isCenterDescendant & isLeftDescendant) | (isCenterDescendant & isRightDescendant) | (isLeftDescendant & isRightDescendant)){
            answer = root;
        }
        if(isLeftDescendant | isRightDescendant | isCenterDescendant) return true;
        return false;
    }
}

 

정답코드2입니다.

이 코드의 경우 특이점은, 만약 왼쪽 트리에만 값이 반횐되고, 오른쪽 트리가 NULL이라면, 왼쪽트리가 반드시 LCA입니다.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //기저 사례 : root가 null이거나 p 또는 q 중 하나와 같으면 root 반환
        if(root == null || root == p || root == q){
            return root;
        }

        //왼쪽과 오른쪽 서브트리 탐색
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        //양쪽에서 p, q를 찾았으면 현재 노드가 LCA
        if(left != null && right != null){
            return root;
        }

        //p와 q가 한쪽 서브트리에만 있는 경우, 해당 서브트리의 결과를 반환
        return (left != null) ? left:right;
    }
}