LeetCode——99. 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?

この問題の大まかな意味は、1本の二叉探索木の中で、2つのノードの位置が交換され、この二叉探索木に間違いが発生したので、それらを交換して、この二叉探索木を復元させることです.同時に,できるだけ空間複雑度を最適化し,最終的には定数レベルの空間複雑度のみを用いることができる.実は二叉探索ツリーを中順に遍歴するのは,秩序配列を遍歴することに相当する.では、O(n)の空間的複雑さだけなら、実は簡単です.私たちは直接中順に遍歴し、すべての点を読み出し、listに保存します.次にlistをソートし(listは完全に秩序化されていないため、ノードが交換されている)、最後に元のツリーの中順に遍歴し、listの要素をツリーのノードに順番に付与すればよい.コードは次のとおりです.

    public void recoverTree(TreeNode root) {
        if(root == null)
            return;
        List tempList = new ArrayList<>();
        inorderTravel(root, tempList);
        Collections.sort(tempList);
        inorderInit(root, tempList);

    }

    public void inorderTravel(TreeNode root, List tempList) {
        if(root == null)
            return;
        inorderTravel(root.left, tempList);
        tempList.add(root.val);
        inorderTravel(root.right, tempList);
    }

    public void inorderInit(TreeNode root, List tempList) {
        if(root == null)
            return;
        inorderInit(root.left, tempList);
        root.val = tempList.get(0);
        tempList.remove(0);
        inorderInit(root.right, tempList);
    }

定数級空間の複雑さについては,実は考え方も上の解法とあまり差がない.新しいリストに不完全な配列を読み込むことができる以上、私はなぜこの二叉検索ツリーで直接操作しないのでしょうか.私は直接中順に遍歴して、それを秩序配列の遍歴と見なして、それから2つのindexで最初のエラーの場所と2番目のエラーの場所を保存して、それから直接値を交換します(私は最初からノードの位置を交換しようと思っていましたが、結果的に操作過程が複雑で、コードも多くて、まだエラーが発生しやすい)、解決したのではないでしょうか.コードは次のとおりです.

    TreeNode firstElement = null;
    TreeNode secondElement = null;
    TreeNode prevElement = new TreeNode(Integer.MIN_VALUE);
    public void recoverTree(TreeNode root) {
        traverse(root);
        int temp = firstElement.val;
        firstElement.val = secondElement.val;
        secondElement.val = temp;
    }

    private void traverse(TreeNode root) {
        if (root == null)
            return;

        traverse(root.left);
        if (firstElement == null && prevElement.val >= root.val) {
            firstElement = prevElement;
        }

        if (firstElement != null && prevElement.val >= root.val) {
            secondElement = root;
        }        
        prevElement = root;
        traverse(root.right);
    }

だから、この問題は難しくありません.核心は、この二叉検索木を秩序ある配列として見ることです.この問題は、二叉検索ツリーを中順遍歴して秩序配列のモデルに変換することを考えることができます.そうすると、この問題はso easyになります.だから、複雑で処理しにくいデータ構造に遭遇することがあります.私たちはそれを対応しやすいモデルに変換することを学ばなければなりません.関連問題は迎刃して解くことができます.私のブログを見てくれてありがとう.わからないところがあったり、間違ったところがあったりしたら、指摘してください.ありがとうございます.もし皆さんが私のブログが好きなら、私にもいいですね.あなたたちのいいねは私の原動力です!