Leetcode - 99. Recover Binary Search Tree

문제

딱 한쌍의 노드를 swap해야 정상적인 BST가 되는 트리가 주어진다. 이 트리를 BST로 고쳐라.

아이디어

• 기본적으로 tree를 inorder 순회
• 순회하면서 두개의 노드를 선정하는 방법.
• 잘못된 지점은 BST는 순회시 현재 노드가 이전노드보다 값이 작을 때.
• 순회시 첫번째로 발견된 지점과 마지막으로 발견된 지점이 최종 swap대상이다. 아래 코드는 이걸 찾는 알고리즘이다. (해설을 참고함)
• 순회 순서상 첫번째로 만나는 target 1은 처음 정렬상태가 어긋나는 노드이다. 이걸 찾고 고정한다(아래 if (n1 == NULL) n1 = prev; 부분). 그 뒤 계속 순회를 하면서 target 1과 비교해서 정렬이 마지막으로 어긋나는 노드를 target2 로 선정.
• 왜 처음과 마지막지점을 찾으면 답이 되는가? 이유는 딱 한쌍의 노드만 잘못배치되어 있기 때문이다.
  • 결국 입력은 패턴이 있는데, 순회 순서가 5-2-3-4-1 4-2-3-1 5-3-1 1-3-2-4 이런 종류만 트리의 입력으로 들어올 수 있음. 정렬---(target1)---정렬----(target2)---정렬 (정렬 지점은 없을수도 있음)

해결 O(N) / O(1)

struct TreeNode *n1 = NULL, *n2 = NULL, *prev = NULL;

void inorder(struct TreeNode* root) 
{
    if (root == NULL)
        return;
    inorder(root->left);
    //printf("%d ", root->val);
    if (prev && root->val < prev->val) {
        n2 = root; // search the final target 2
        if (n1 == NULL) n1 = prev; // fix the target 1
        else return;
    } 
    prev = root;
    inorder(root->right);
    return; 
}

void swap(struct TreeNode* a, struct TreeNode* b)
{
    if (!a || !b)
        fprintf(stderr, "failed to find targets\n");
    int tmp = a->val;
    a->val = b->val;
    b->val = tmp;
}

void recoverTree(struct TreeNode* root){
    n1 = NULL, n2 = NULL, prev = NULL;
    inorder(root);
    swap(n1, n2);
    return;
}