4.6 후속자

문제 

이진 탐색 트리에서 주어진 노드의 '다음' 노드( 중위 후속자 ) 를 찾는 알고리즘을 작성하라. 각 노드에는 부모 노드를 가리키는 링크가 존재한다고 가정하자. 

 

해결법

이진 트리에서 중위 후속자를 찾는방법

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