Study/Interview준비
4.6 후속자
DoRoMii
2019. 7. 28. 20:53
728x90
문제
이진 탐색 트리에서 주어진 노드의 '다음' 노드( 중위 후속자 ) 를 찾는 알고리즘을 작성하라. 각 노드에는 부모 노드를 가리키는 링크가 존재한다고 가정하자.
해결법
이진 트리에서 중위 후속자를 찾는방법
1. 오른쪽 노드가 있다면 오른쪽 노드의 가장 왼쪽 노드
2. 오른족 노드가 없다면 현재 노드가 왼쪽 노드일때까지 부모를 타고 올라가기
def get_left(node):
while node.left is not None :
node = node.left
return node
def Solution(node):
if node is None : return None
if node.right is not None :
return get_left(node.right)
else :
cur = node
p = node.parent
while cur is not None and cur != p.left :
cur = p
p = p.parent
return p