leetcode 99. 恢复二叉搜索树（C++）

今天药忘吃喽~ 2023-07-18 06:21 18阅读 0赞

# 题目 #

二叉搜索树中的**两个节点**被**错误地交换**。请在**不改变其结构**的情况下，恢复这棵树。

示例 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

进阶:  
使用 O(n) 空间复杂度的解法很容易实现。  
你能想出一个只使用常数空间的解决方案吗？

来源：[99. 恢复二叉搜索树 - 力扣（LeetCode）][99. _ - _LeetCode]  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。  
算法来自官方题解——>[恢复二叉搜索树 - 恢复二叉搜索树 - 力扣（LeetCode）][- _ - _LeetCode]

# 中序遍历法 #

*  若要找到交换的节点，就记录中序遍历中的最后一个节点 pred（即当前节点的前置节点），并与当前节点的值进行比较。如果当前节点的值小于前置节点 pred 的值，说明该节点是交换节点之一。  
    交换的节点只有两个，因此在确定了第二个交换节点以后，可以终止遍历。

代码如下：

class Solution { 
    public:
        void recoverTree(TreeNode* root) { 
            if(!root)   return ;
            vector<TreeNode*> stack;
            TreeNode* x = NULL;
            TreeNode* y = NULL;
            TreeNode* pred = NULL;
            while(!stack.empty() || root){ 
                while(root){ 
                    stack.push_back(root);
                    root = root->left;
                }
                root = stack.back();
                stack.pop_back();
                if(pred && root->val < pred->val){ 
                    y = root;
                    if(!x)  x = pred;
                    else    break;
                }
                pred = root;
                root = root->right;
            }
            int temp = x->val;
            x->val = y->val;
            y->val = temp;
        }
    };

结果：  
![在这里插入图片描述][20200324235043392.png]

[99. _ - _LeetCode]: https://leetcode-cn.com/problems/recover-binary-search-tree
[- _ - _LeetCode]: https://leetcode-cn.com/problems/recover-binary-search-tree/solution/hui-fu-er-cha-sou-suo-shu-by-leetcode/
[20200324235043392.png]: /images/20230528/e4fd45881e4d45198b1aacbeb1e25d80.png