문제

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

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

문제해석

전체 노드 root와 두 가지 노드 p, q가 주어지고, 주어진 두 노드 p,q의 가장 낮은 레벨의 공통 조상을 찾는 문제이다.
그걸 LCA(Lowest Common Ancestor)라 부르는데, p q 노드 중 한 노드가 그 스스로 자손이 되는걸 허용한다고 한다. 즉 위 트리 그림에서 p=5, q=2라면 p가q의 부모 노드면서 p의 자식 노드는 p이다는 명제도 허용한다는 뜻이다. 그래서 이 경우는 LCA가 p인 5가 된다.

풀이

• 풀이에 앞서

소스코드 작성 이전에 어느정도 도식화로 수도코드가 분명해져야 코드 작성이 가능해진다 당연한 말 같지만 어설프게 수도코드가 정의되면 코드작성시 막히니까 수도코드를 어느정도는 확실히 작성하고 들어가야 한다.

이 문제를 푸는데 우선 LCA가 발견되는 케이스를 나눠 생각해 봐야 한다.

첫번째 케이스는,

루트 노드에서 좌측 자식 노드에 p가 발견되고 우측 자식 노드에 q가 발견되면
p노드랑 q노드를 계속 위로 return 시켜 만나는 상위 노드가 LCA가 된다. 그림에선 Root 노드라고 적었는데 이게 Root 노드가 LCA일 수 있고, 루트 위에 위에.. 상위 노드가 LCA가 될 수 있다. 즉 왼쪽, 오른쪽 사이드 한쪽씩 p,q 또는 q,p가 발견되는 경우. 이 경우는 (left, right,가 p,q || q,p라고 생각했을때,, ) if(left && right) return root(해당노드) 로 LCA를 구할 수 있다.

두 번째 케이스는,

left or right 한쪽 사이드에 p,q 둘중 하나가 조상 노드고, 둘중 하나가 자식 노드로 발견 될 때이다. 위 그림의 왼쪽 케이스 p가 조상, q가 후손 노드라 하면 q가 발견되어 q에서 return q를 해준다 하더라도, 결국 LCA는 P가 되어 P를 return 해줘야 한다. 즉 return q는 최종 리턴에서 무시된다, p의 우측 자식 노드도 무시되므로 탐색할 필요가 없으므로, 따라서 p를 발견하면 거기서 return node하고 탈출하면 된다. 그러면 p의 부모 루트에서 반대편(왼쪽 그림에선 right side)부터 탐색을 계속한다. 반대쪽 q가 발견된다면 return node를 하게 되고, 즉 return p && return q 가 만나는 노드가 LCA가 된다. 만약 q가 p의 서브트리에 있어서 탐색 하지 못한다면 p가 LCA가 되고 가장 상위 root에서 반환하게 하면 된다. .

반대로 위의 오른쪽 그림 부분처럼 q가 조상, p가 후손일때도 이해를 돕고자 설명하자면, q발견시 return q를 해주고, q의 서브트리를 탐색할 필요 없다. 탐색 없이 코드 상단에서 if(node === q )return q 를 해주면 q의 부모노드에서는 return 값을 받을수 있으니 받고, q가 오른쪽 자식 노드였으니, other side, 왼쪽 노드 사이드부터 탐색 해주면 된다. 만약 p가 있으면 return p를 해당 노드 부모에서 사용할 수 있도록 해준다.

즉 어느 노드에서
1. left, right 중 한 부분에서 p,q가 발견되면 => return p || q node
2. 위처럼 return 하면 p 또는 q가 발견된 노드의 서브트리만 탐색중지 되고, 부모노드부턴 계속 탐색한다.
3. 만약 탐색하다가,
 3-1. p나 q를 발견하지 못하면 (=즉 p또는 q 서브트리에 q 또는 q가 있는 경우 = 첫번째 케이스 사진) 최상위 root에선 p,q중 발견한 노드를 return 해준다.
 3-2. p나 q를 발견한다면 (=즉 p와 q가 상위루트 자손으로 left, right 양분해 있는 경우 = 두번째 케이스 사진)
이 경우는 p가 left q가 right 부분에 있었다면 const left = dsf(node.left), const right = dsf(node.right) 로 부모트리에서 계속 받아올수 있으니깐, 받다가 상위 어느 부모노드에 left, right가 만나는 곳에서 return 해주면 된다.

코드화

function dsf(root, p, q){
  if(!root || p === root || q === root) return root;
  const left = dsf(root.left, p, q);
  const right = dsf(root.right, p, q);
  
  return ((left && right) ? root : (left || right)) 
}

괜찮은 풀이 영상 but Eng youtube : https://www.youtube.com/watch?v=KobQcxdaZKY