[leetcode] Recover Binary Search Tree

ミス
問題条件の把握に失敗しました:問題には2つのノードの配置エラーが書かれています
正しいバイナリツリーの意味
バイナリツリーが正しいかどうかを決定するときは、ルートの左側のサブアイテムと右側のサブアイテムだけを考慮することはできません.
たとえば、106,220 NULL NULL 5 23の場合、ルートの左側のサブアイテムの右側のサブアイテムのみを考慮すると、正しい状況が発生します.
10の子が6と20の場合→true
20の子供が5と23の場合→true
結果→true
注意事項
問題には2つのノードの配置エラー→2つのノードを見つけて交換すればよいと書かれています.
ソートエラーの2つのノードには、次の特徴があります.

最初のエラーノードは、次のエラーノードよりも大きい.→前のノードが現在のノードより大きい場合は、最初のエラーノードです.

の2番目のエラーノードは、前の順序のノードよりも小さい.

これは,大きな値が前方に,小さな値が後方に向かうことによる現象である.
→最悪の場合、2つのノードを検索するのにN回必要です.N次再帰はO(N)の空間的複雑さを要求する.付加的な問題に不満がある.(その他の問題:O(1)時間で解決)
その他の質問→Morris Transversalを使用します.
に答える
ツリーの値を電位巡回で抽出しvectorに読み込み、その値をソートします.
次に、これらの値を電位巡回挿入し直します.
inorderの基本コード

private void traverse (TreeNode root) {
   if (root == null)
      return;
   traverse(root.left);
   // Do some business
   traverse(root.right);
}

コード#コード#
C++:私が作ったのは、一度に2回→同じことを2回します.能率が落ちる

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    vector <int> _arr;
public:
    void inorder(TreeNode* root){
        if(root==NULL) return;
        inorder(root->left);
        _arr.push_back(root->val);
        inorder(root->right);
    }
    
    void recover(TreeNode* root,int&idx){
        if(root==NULL) return;
        recover(root->left,idx);
        root->val = _arr[idx++];
        recover(root->right,idx);
    }
    
    void recoverTree(TreeNode* root) {
        inorder(root);
        sort(_arr.begin(),_arr.end());
        int idx = 0;
        recover(root,idx);
    }
};

C++:順番

//작성예정