[Grind75-LeeCode] Lowest Common Ancestor of a Binary Tree JAVA

반응형

728x90

[Grind75-LeeCode] Lowest Common Ancestor of a Binary Tree - Medium

---

접근

• dfs

---

풀이

이진트리에서 최저 공통 조상 노드를 찾는 문제이다. 이전에 거의 흡사한 문제를 풀었던 적이 있다.

2024.10.08 - [알고리즘/코딩테스트-Grind75] - [Grind75-LeetCode] Lowest Common Ancestor of a Binary Search Tree JAVA

[Grind75-LeetCode] Lowest Common Ancestor of a Binary Search Tree JAVA

위 문제는 똑같이 공통 조상 노드를 찾는 문제이다. 그러나 다른 점으로 위의 문제는 이진 탐색 트리(BST)에서 최저 공통 조상 노드를 찾는 것이었고 이번 문제는 이진트리(Binary Tree)에서 최저 공통 조상 노드를 찾아야 하는 차이가 있다. 이진 탐색 트리는 루트 노드를 기준으로 양쪽 서브트리의 값이 정렬된 상태로 존재하지만 이진트리의 경우 루트 노드가 최대 2개의 자식 노드를 가지는 것만 만족하는 트리이다. 그렇기 때문에 단순 값을 통해 비교했던 위의 경우와는 다른 방식으로 접근해야 한다. 최저 공통 조상 노드에 대한 부분은 윗글을 참고하길 바란다.

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

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

 

중간에 양쪽 서브트리로 재귀 호출을 통한 dfs를 진행하는 부분 외에 다 반환 조건을 다룬 코드로 위에서부터 설명하겠다. 처음 나오는 조건으로 루트 노드가 비었거나 루트 노드가 p, q인 경우 루트 노드를 반환하는 조건이다. 루트 노드가 비었다는 것은 트리 자체가 존재하지 않거나 재귀 호출 시 서브트리가 존재하지 않는 경우이다. 그 경우 null을 반환하여 해당 경로에 트리가 존재하지 않는다는 사실을 반환한다. 루트 노드가 p, q와 같은 경우 트리가 시작되는 루트 노드의 경우 바로 공통 최저 조상 노드가 되므로 루트 노드를 결과로 반환하게 되고 그렇지 않은 경우 해당 목표 노드를 발견하여 left, right 중 하나로 반환되게 된다. 또한 루트 노드를 기준으로 찾고자 하는 p, q 두 노드가 같은 쪽 서브트리에 위치하게 된다면 해당 조건으로 결과가 반환되게 된다. 

	if (left != null && right != null) {
            return root;
        }

        return left != null ? left : right;
    }

루트 노드가 비어있지 않고 p, q 와도 다른 경우 재귀를 통해 얻어온 left, right 노드를 검사하여 반환하게 된다. 만약 left, right 두 노드가 비어있지 않다면 양쪽 서브트리에서 각 목표 노드를 찾은 것으로 현재 루트 노드를 최저 공통 조상 노드로 반환한다. left, right 둘 중 하나가 비어있다면 비어있지 않은 곳을 결과로 반환한다. 

dfs

이 문제도 여러번 제출을 하다 보면 6ms~7ms를 왔다 갔다 하기에 7ms이상으로 통과한다면 좋은 방법이라고 할 수 있을 거 같다. 

---

전체 코드

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

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

        if (left != null && right != null) {
            return root;
        }

        return left != null ? left : right;
    }