Tree 활용 [입문편] - Lowest Common Ancestor of aBinary Tree

LeetCode - The World's Leading Online Programming Learning Platform

문제

해석

중요한 점은 자기 자신을 포함한 것을 조상이라고 생각하는 것

case1

• 주어진 노드 : 5, 4
• 주어진 노드의 조상 : 3
• 공통 노드 : 3
• 가장 낮은 공통 노드 : 3

case2

• 주어진 노드 : 5, 4
• 주어진 노드의 조상 : 4, 2, 5, 3
• 공통 노드 : 3, 5
• 가장 낮은 공통 노드 : 5

case3

• 주어진 노드 : 6, 4
• 주어진 노드의 조상 : 4, 2, 6, 5, 3
• 공통 노드 : 5, 3
• 가장 낮은 공통 노드 : 5

구현

PostOrder 방식

문제 구현은 이 그림을 기준으로 한다. 여기서 q가 오타인데 7이 아니라 4이다

포인트는 주어진 노드에서 거슬러 올라왔을 때 left와 right 값이 모두 존재한다면 그 root는 공통된 조상인 것으로 간주한다

이게 무슨말인지 이해가 안갈수도 있는데 코드를 살펴보면 바로 감이 잡힐듯

def LCA(root, p, q):
		if root == None:
			return None

		# 여기선 root(3)이 아닌 5의 트리 세상
		# 그리고 재귀 될때마다 해당 자식들의 트리 세상으로 변한다
		left = LCA(root.left, p , q)

		# 여기선 root(3)이 아닌 1의 트리 세상
  	# 그리고 재귀 될때마다 해당 자식들의 트리 세상으로 변한다
		right = LCA(root.right,p, q)

		# 만약 root가 6이 되었을 때 6이(root 값이) p와 같으니까 6을 반환함
		if root == p or root == q:
			return root
		# left right 두개 다 None이 아닐땐 root 반환
		# 만약 left와 right 둘다 None이라면 이 코드는 pass
		elif left and right:
			return root
		# left 와 right가 둘다 None 이면 left 혹은 right를 반환
		# 어차피 둘다 None이라 None이 반환됨
		# 만약 둘중에 return 값이 있다면 값이 있는 것을 반환
		return left or right	

LCA([3,5,1,6,2,0,8,None,None,7,4], 6, 4)

문제

해석

중요한 점은 자기 자신을 포함한 것을 조상이라고 생각하는 것

case1

• 주어진 노드 : 5, 4
• 주어진 노드의 조상 : 3
• 공통 노드 : 3
• 가장 낮은 공통 노드 : 3

case2

• 주어진 노드 : 5, 4
• 주어진 노드의 조상 : 4, 2, 5, 3
• 공통 노드 : 3, 5
• 가장 낮은 공통 노드 : 5

case3

• 주어진 노드 : 6, 4
• 주어진 노드의 조상 : 4, 2, 6, 5, 3
• 공통 노드 : 5, 3
• 가장 낮은 공통 노드 : 5

구현

PostOrder 방식

문제 구현은 이 그림을 기준으로 한다. 여기서 q가 오타인데 7이 아니라 4이다

포인트는 주어진 노드에서 거슬러 올라왔을 때 left와 right 값이 모두 존재한다면 그 root는 공통된 조상인 것으로 간주한다

이게 무슨말인지 이해가 안갈수도 있는데 코드를 살펴보면 바로 감이 잡힐듯

def LCA(root, p, q):
		if root == None:
			return None

		# 여기선 root(3)이 아닌 5의 트리 세상
		# 그리고 재귀 될때마다 해당 자식들의 트리 세상으로 변한다
		left = LCA(root.left, p , q)

		# 여기선 root(3)이 아닌 1의 트리 세상
  	# 그리고 재귀 될때마다 해당 자식들의 트리 세상으로 변한다
		right = LCA(root.right,p, q)

		# 만약 root가 6이 되었을 때 6이(root 값이) p와 같으니까 6을 반환함
		if root == p or root == q:
			return root
		# left right 두개 다 None이 아닐땐 root 반환
		# 만약 left와 right 둘다 None이라면 이 코드는 pass
		elif left and right:
			return root
		# left 와 right가 둘다 None 이면 left 혹은 right를 반환
		# 어차피 둘다 None이라 None이 반환됨
		# 만약 둘중에 return 값이 있다면 값이 있는 것을 반환
		return left or right	

LCA([3,5,1,6,2,0,8,None,None,7,4], 6, 4)