Inorder Successor in BST II

Inorder Successor in BST II

Explore - LeetCode

- 문제 내용 : binary tree에서 특정 노드를 input으로 주면 inorder successor(다음에 나올 노드)로 올 노드를 Return

- 접근 방법 :

inorder로 나올수 있는 경우의 수를 줄여 가면서 Case를 나누었다.

일단 preorder, inorder, postorder를 이해 해야한다.

상기의 붉은 색이 Root 라고 할때 Root의 위치를 나타낸다. Pre는 맨 처음, in은 중간, Post는 마지막에 Root Node를 표현 하게 된다.

여기서 successor는 주어진 노드의 다음에 나올 노드를 나타낸다.

입력으로 주어진 node가 5라고 하면 다음에 올 successor 노드는 2가 된다. 

- Case 1 : 주어진 노드에 오른쪽에 node가 있는 경우

이 경우는 무조건 오른쪽에 있는 node가 답이 된다. 단, 우측 노드가 마지막 노드가 아니라면 우측 노드의 좌측 노드가 다음 노드가 된다.

그래서 우측 노드에 왼쪽이 있다면 5 node의 자리를 6으로 교체 하면 된다.

 

- Case 2 : 주어진 노드에 우측 노드가 없고 Parent Node의 우측에 존재할 경우, Parent를 조회 대상으로 변경해 줘야 한다.

입력이 5일 경우

입력이 3일 경우

상기 두가지 Case를 생각 하고 하면 되는데

입력이 5일 경우 조회 하고자 하는 node를 1로 변경 해줘야 한다. 이게 왜 되는 거냐면 1은 이미 Print가 됬다고 보기때문에 1의 next가 5의 다음이 되기 때문이다.

만약 3과 같이 Parent가 더이상 올라갈 곳이 없다면 next가 없기 때문에 null로 처리 하면 된다.

function inorderSuccessor(node) {
    if (node == null) {
        return null;
    }
    if (node.right) {
        let next = node.right;
        while(next.left != null){
            next = next.left
        }
        return next;
    } else {
        let parent = node.parent;

        if(parent == null){
            return null;
        }

        if (parent.left == node) {
            return parent;
        }

        if (parent.right == node) {
            parent.right = null;
            return inorderSuccessor(parent);
        }
    }
}