LeetCode - 236. Lowest Common Ancestor of a Binary Tree

 

 

문제 분석

이 문제는 이진 트리에서 두 노드 p,q가 주어졌을때, 가장 낮은 공통 조상을 찾는 문제임.

LCA: 어떤 두 노드의 가장 가까운 공통 조상

        3
       / \
      5   1
     / \ / \
    6  2 0  8
      / \
     7   4

만약 이 트리에서 p=5, q=1일때 공통 조상은 3이됨

p=5, q=4라면 공통 조상은 5가됨 (자기 자신이 조상이됨)

 

class Solution {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
      
        if (root == null || root == p || root == q) {
            return root;
        }

        TreeNode leftSub = lowestCommonAncestor(root.left, p, q);
        TreeNode rightSub = lowestCommonAncestor(root.right, p, q);

        if (leftSub != null && rightSub != null) {
            return root;
        }

        return leftSub != null ? leftSub : rightSub;



    }

}

 

해결 과정

 

종료조건을 설정해줍니다.

노드가 null(트리의 끝에 도달했을때)이거나 현재 노드가 입력된 p거나 q이면 해당 노드를 반환시켜줍니다.

TreeNode leftSub = lowestCommonAncestor(root. left, p, q);

TreeNode rightSub = lowestCommonAncestor(root.right, p, q);

현재 노드의 왼쪽, 오른쪽 자식 노드로 재귀적 탐색을 진행해줍니다.

-> 각각 p나 q가 발견되면 해당 노드가 위로 전달됨.

if (leftSub != null && rightSub != null) {

return root;

}

 

왼쪽과 오른쪽에서 각각 하나씩 노드가 발견된 경우에는 현재 root가 공통 조상

(p는 왼쪽 서브트리, q는 오른쪽 서브트리에서 발견됨)

 

return leftSub != null? leftSub : rightSub;

-> 만약 둘중 하나만 null이 아니면 그 노드를 계속 위로 전달해주기

-> 둘다 null이면 null이 리턴됨 -> 아무것도 찾지못함