[LeetCode] 236. Lowest Common Ancestor of a Binary Tree

 

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

불러오는 중입니다...

---

1. Problem 

이진트리가 주어졌을 때, 두 개의 주어진 노드 p, q의 가장 작은 공통 조상 노드를 찾아라.

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

 

 

2. Algorithm

나는 p, q의 공통 조상 노드라는 것은 해당 노드를 root로 하고 탐색을 하면, p, q를 모두 찾을 수 있다는 것을 뜻한다고 생각했다. 이것은 즉 트리에서 해당 노드를 기준으로 자손 노드 중에 p, q가 존재한다는 의미. 따라서 root부터 dfs로 모든 노드를 탐색하며, p와 q가 자손 노드에 존재하는지 확인하는 방법을 사용했다. 

I thought the ANCESTOR NODE means that the node which can find both of p and q when we start to search from the node.  So I started searching p, q from every node and then find the nearest location from p, q.

 

Step 1. dfs로 탐색을 시작한다. 다음 isAncestorOfPQ함수를 사용해 p와 q의 조상 노드인 방향으로만 탐색을 계속 진행하므로 탐색할 노드의 개수는 대략 log n으로 줄어든다. (FBT라는 보장이 없기 때문에, 대략적으로만! 최악으로는 n이 될 수도 있음) // O(n)

Start to search with dfs. We will continue to searching in direction of ancestor node, so the time complexity of dfs decrease to approximately O(logn). (but there is no guarantee the tree is FBT, so it becomes O(n) in the worst situation)

 

Step 2. isAncestorOfPQ() 함수를 사용하여 다시 dfs를 사용해 p와 q가 모두 존재하는지 확인해준다. 존재하지 않는다면 그 노드 이후의 자손 노드는 탐색하지 않는다. 존재하는 경우에는 그 자식 노드로 이동한다. (가장 가까운 조상 노드를 찾아야 하기 때문) // O(k)

With isAncestorOfPQ() function, find node p and q from root Node. Stop searching if they don't exist, Or move to children node(left, right) if they do.

 

Step 3. 자식 노드를 모두 방문한 후, 다시 재귀적으로 돌아와 자식 노드가 모두 null인 경우(조상이 아니거나, 단말 노드인 경우)에는 현재 노드를 리턴하고, 자식 노드 중에 하나라도 null이 아닌 경우(즉, p, q의 조상 노드인 경우) 에는 해당 노드를 리턴한다.

After visited all Children nodes, comeback to node reculsively. If all the childrens are null and the return current node, if not, then return child which is not null.

 

따라서, 시간복잡도는 O(n*k)로 O(n^2) 솔루션이다.. 느린 솔루션..

좋은 솔루션은 아니니, 보다 나은 코드도 함께 첨부하겠다.

My code is O(n^2) solution. tooooooo slow.. So check another better code that I added at the retrospective part.

/**
 * 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 node, TreeNode p, TreeNode q) {
        if(node == null) return null;
        if(!isAncestorOfPQ(node, p, q)) return null;
        TreeNode left = lowestCommonAncestor(node.left, p, q);
        TreeNode right = lowestCommonAncestor(node.right, p, q);
        return (left == null && right == null)? node : (left == null)? right: left;
    }
    boolean isAncestorOfPQ(TreeNode node, TreeNode p, TreeNode q){ 
        return dfs(node, p) && dfs(node, q);
    }
    boolean dfs(TreeNode node, TreeNode p) {
        if(node == null) return false;
        if(node.val == p.val) return true;
        boolean left = dfs(node.left, p);
        boolean right = dfs(node.right, p);
        return left||right;
    }
}

 

 

3. retrospective

엄청나게 느린 속도로 통과를 했다. 아무래도 중복으로 검색을 하는 부분이 많아서 속도가 느려진 것 같다. 

Super slow but passed. I think my code search same node multiple times. Here is better code with better speed.

 

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        if (root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        return (left != null && right != null)? root: (left == null)? right:left;
    }
}

이 코드는 다른 사람들의 코드를 참고하여 작성해보았는데, 아직 잘 이해가 되지 않는다. 좀 더 이해하려고 노력해본 뒤에 업데이트 해야겠다.

I wrote this code refer to other solutions, but it is hard to understand. I will update after I understand it.