[leetcode] 99. Recover Binary Search Tree解題レポート

タイトルリンク:https://leetcode.com/problems/recover-binary-search-tree/
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Note:
A solution using O(
n
) space is pretty straight forward. Could you devise a constant space solution?
confused what  "{1,#,2,3}"  means? > read more on how binary tree is serialized on OJ.
構想:二叉探索木の中序遍歴で実現することができ、この方式は実際にlog(n)の空間を使ったが、一つのアルゴリズムにとってlog(n)は定数空間であり、私はかつて私たちのアルゴリズム教授に教えてもらったことがある.
まずnaiveの方法を見てみましょう.すなわち、O(n)を使用する空間の複雑さはどのように解決すべきか.
我々は1つの配列を開くことができて、中序は木を遍歴して、そしてそれを順番に配列の中で保存します.もし1つの正常な2つのフォークの捜索木ならば完全に秩序があります.しかしその中の2つのノードを交換した後に2つのノードが誤った位置に現れます.栗を挙げます:[1,2,3,4,5,6]これは正常な2つのフォークの捜索数のシーケンスで、2つのノードが交換と[1,5,3,4,2,6]となる.
では、どのようにしてこの2つの交換のノードを見つけますか?大きな数が前に移動すると、彼は必ず彼の後ろの数より大きくなることを知っています.つまり、私たちが配列を遍歴したときに出会った最初の後ろの結点より大きい結点は交換された大きな結点です.それでは、後ろの小さな結点を交換しても同じ理屈で見つけることができます.つまり、この小さな結点は必ず前の結点より小さいです.しかし、交换する2つの结点が隣接する结点でなければ、2つの结点が前の结点より小さいことがあります.大きな结点が前に交换されると、彼は必ず后の结点より大きくなり、それから本当に交换する过去の小さな结点も前の结点より小さくなります.だから、私たちが见つけるのは最后の结点が前の结点より小さい结点です.
上の理論があれば、配列の中で2つの失序のノードを簡単に見つけることができます.それからその値を交換すればいいです.
さて、O(n)空間の複雑さを用いるアルゴリズムを知っている以上、ノードを保存する必要はありません.なぜなら、この2つのノードを直接中序遍歴で直接見つけることができるからです.しかし、現在のノードの前のノードという別のタグが必要です.これにより、上記のアルゴリズムを復元することができます.
コードは次のとおりです.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void inOrder(TreeNode* root)
    {
        if(!root) return;
        inOrder(root->left);
        if(pre && pre->val > root->val)
        {
            if(!first) first = pre;
            second = root;
        }
        pre = root;
        inOrder(root->right);
    }
    
    void recoverTree(TreeNode* root) {
        if(!root) return;
        inOrder(root);
        swap(first->val, second->val);
    }
private:
    TreeNode *pre =NULL, *first =NULL, *second=NULL;
};

参考:どのブログが分からない