난이도 - Medium
Intuition
이 문제는 여러 방법으로 풀 수 있다. 일단 우리는 p와 q노드를 찾은 뒤, 위로 다시 올라가는 backtracking을 사용하여 lca를 찾아야 한다.
1) Recursive Approach
이 방식은 트리를 DFS방식으로 p와 q노드를 먼저 찾는 방식이다. 그리고는 찾은 결과를 boolean flag를 사용하여 lca를 찾아내는 방법이다.
1. 루트 노드부터 시작해서 DFS 탐색을 시작한다.
2. 만약 현재 노드가 p또는 q이면, mid를 True로 설정한다. 그리고 DFS탐색을 계속한다.
3. 만약 왼쪽이나 오른쪽 브랜치가 True를 반환하면, 두개중 하나의 노드는 발견이 된것이다.
4. 따라서 left, mid, right중 2개가 True를 반환하면, 우리는 현재 lca에 있는것이다. 따라서 lca를 저장한다.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
ans = None
def helper(node: 'TreeNode'):
if not node:
return False
nonlocal ans
left = helper(node.left)
right = helper(node.right)
mid = node == p or node == q
if mid + left + right >= 2:
ans = node
return mid or left or right
helper(root)
return ans
Time Complexity: O(n) 여기서 n은 binary tree의 노드 개수이다. 최악의 경우에 우리는 모든 노드를 탐색해야 하기 때문이다.
Space Complexity: O(n) Recursive stack을 사용하므로 최대 용량 사용은 n이 된다(Binary Tree가 한쪽으로만 자식을 가지고 있을 최악의 경우)
2) Iterative using parent pointers
우리가 만약 parent pointers을 사용할 수 있다면, p와 q노드에서 ancestors로 다시 돌아갈 수 있다. 그 중 처음으로 마주치는 공통 ancestor가 LCA 노드가 된다.
1. 루트부터 시작해서 탐색을 시작한다.
2. p와 q를 둘 다 찾을때까지 탐색한다, 그러면서 parent pointer를 dict에 저장한다.
3. p와 q를 찾으면, p의 ancestors을 ancestors라는 set에 저장한다.
4. q도 마찬가지로 ancestors을 찾아서 만약 p의 ancestors에 있으면, 그것이 LCA이다.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
stack = [root]
parent = {root: None}
while p not in parent or q not in parent:
node = stack.pop()
if node.left:
parent[node.left] = node
stack.append(node.left)
if node.right:
parent[node.right] = node
stack.append(node.right)
ancestors = set()
while p:
ancestors.add(p)
p = parent[p]
while q not in ancestors:
q = parent[q]
return qTime Complexity: O(n) 여기서 n은 binary tree의 노드 개수이다. 최악의 경우에 우리는 모든 노드를 탐색해야 하기 때문이다.
Space Complexity: O(n) Parent Pointer dict and the ancestor set들의 stack을 사용하므로 최대 용량 사용은 n이 된다(Binary Tree가 한쪽으로만 자식을 가지고 있을 최악의 경우)
3) Iterative without parent pointers
우리는 2) 접근법에서 backtracking process를 사용했다. 사실 우리는 backtracking process를 생략할 수 있다. 이번 접근법에는 우리는 항상 LCA가 될 수 있는 포인터들을 가지고 있고 조건의 만족하는 경우 그 포인터를 답으로 반환할 것이다.
1. 루트 노드부터 시작한다.
2. stack에 (root, root_state)를 집어넣는다. root_state는 하나 혹은 두개의 childeren이 탐색을 아직 하지 않았을 상태를 나타낸다.
3. 스택이 남아있는 상태라면, top 원소를 pop하여 (parent_node, parent_state)를 가져온다.
4. parent_node의 자식노드들을 탐색하기 전에, 먼저 parent_node이 p또는 q인지 확인한다.
5. p와 q를 찾으면, one_node_found값을 True로 설정한다. 그리고 LCA_index에 스택의 top index를 트랙킹하면서 LCA를 찾아간다.
6. 두번째로 parent_node == p or parent_node == q 이면, 우리는 p q를 다 찾은것이고 LCA를 반환해야 한다.
7. 우리는 parent_node의 child 노드들을 방문할때마다 스택에 (parent_node, updated_parent_state)를 넣는다.
8. BOTH_DONE이라는 상태가 있는 노드가 나올때까지 스택을 계속 pop한다.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
BOTH_PENDING = 2
LEFT_DONE = 1
BOTH_DONE = 0
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
stack = [(root, Solution.BOTH_PENDING)]
one_node_found = False
LCA_index = -1
while stack:
parent_node, parent_state = stack[-1]
if parent_state != Solution.BOTH_DONE:
if parent_state == Solution.BOTH_PENDING:
if parent_node == p or parent_node == q:
if one_node_found:
return stack[LCA_index][0]
else:
one_node_found = True
LCA_index = len(stack) - 1
child_node = parent_node.left
else:
child_node = parent_node.right
stack.pop()
stack.append((parent_node, parent_state - 1))
if child_node:
stack.append((child_node, Solution.BOTH_PENDING))
else:
if one_node_found and LCA_index == len(stack) - 1:
LCA_index -= 1
stack.pop()
return NoneTime Complexity: O(n) 여기서 n은 binary tree의 노드 개수이다. 최악의 경우에 우리는 모든 노드를 탐색해야 하기 때문이다.
Space Complexity: O(n) Parent Pointer dict and the ancestor set들의 stack을 사용하므로 최대 용량 사용은 n이 된다(Binary Tree가 한쪽으로만 자식을 가지고 있을 최악의 경우)