Leetcode 99. 二叉探索ツリーC++を復元

Leetcode 99. ツリーの復元
タイトル
ツリー内の2つのノードが誤って交換されました.
構造を変えずに、この木を復元してください.
テストサンプル
1.

  : [1,3,null,null,2]

   1
  /
 3
  \
   2

  : [3,1,null,null,2]

   3
  /
 1
  \
   2

2.

  : [3,1,4,null,null,2]

  3
 / \
1   4
   /
  2

  : [2,1,4,null,null,3]

  2
 / \
1   4
   /
  3

問題解
二叉探索ツリーの場合、中順遍歴の結果は厳密に増加するはずです.題意から分かるように,2つのノードが交換され,すなわち2つの位置が厳密に増加しない.最初の場所で減少が発生し、エラーノードはpreであるべきです.2番目の場所では1回の減少が発生しますが、今回はrootです.もちろん、この2回は同じ位置で発生する可能性があります.私たちはそれぞれこの2つの位置を見つけて交換すればいいです.詳細手順はコードを参照
コード#コード#

	TreeNode *pre=NULL;		//       ，        
    TreeNode *one=NULL;		//              
    TreeNode *two=NULL;		//              
    bool search(TreeNode *root){
     
        if(root == NULL)    return false;
        if(search(root->left))  return true;
        if(pre != NULL && pre->val>root->val){
     
            if(one==NULL){
     
                one = pre;
                two = root;
            }else{
     
                two=root;
                return true;
            } 
        } 
        pre = root;
        if(search(root->right)) return true;
        return false;
    }
    void recoverTree(TreeNode* root) {
     
        search(root);
        swap(one->val,two->val);
    }

ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/recover-binary-search-tree著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.