leetcode：99. 恢复二叉搜索树

题目

给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。

示例 1：
[中等] 99. 恢复二叉搜索树 - 图1

  1. 输入：root = [1,3,null,null,2]
  2. 输出：[3,1,null,null,2]
  3. 解释：3 不能是 1 的左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。

示例 2：
[中等] 99. 恢复二叉搜索树 - 图2

  1. 输入：root = [3,1,4,null,null,2]
  2. 输出：[2,1,4,null,null,3]
  3. 解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。

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

解答 & 代码

解法一：递归中序遍历，空间复杂度 O(logN)

二叉搜索树的中序遍历序列是递增序列，本题的二叉搜索树中有两个节点的值错位，则说明中序遍历序列中有两个元素的位置被交换，使得序列不再有序。
交换递增序列的两个位置，存在两种情况：设有序序列 [1, 2, 3, 4, 5]

  1. 交换相邻的两个元素：eg. 交换 2、3，则序列变为 [1, **3, 2**, 4, 5]
  • 则序列中只存在一处 nums[i] < nums[i+1] 的情况
  1. 交换不相邻的两个元素：eg. 交换 2、5，则序列变为 [1, **5****, 3**, **4, ****2**]
  • 则序列中存在两处 nums[i] < nums[i+1] 的情况

记录两个待交换的错位节点，再交换即可
IMG_7089(20220507-105136).PNG

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. private:
  14.     TreeNode* wrongNode1;    // 第一个错位节点
  15.     TreeNode* wrongNode2;    // 第二个错位节点
  16.     TreeNode* pre;            // 中序遍历前一个节点
  18.     // 中序遍历，寻找两个错位节点
  19.     void inOederFindWrongNodes(TreeNode* root)
  20.     {
  21.         if(root == nullptr)
  22.             return;
  24.         // 递归遍历左子树
  25.         if(root->left)
  26.             inOederFindWrongNodes(root->left);
  28.         // 中序遍历位置：找出两个错位节点
  29.         if(root->val < pre->val)        // 若 root 的值小于中序前一个节点 pre 的值
  30.         {
  31.             if(wrongNode1 == nullptr)    // 若 wrongNode1 为空，则 pre 是第一个错位节点
  32.                 wrongNode1 = pre;
  33.             wrongNode2 = root;            // root 是第二个错位节点
  34.         }
  35.         pre = root;                        // 更新中序遍历序列的 pre 节点为 root
  37.         // 递归遍历右子树
  38.         if(root->right)
  39.             inOederFindWrongNodes(root->right);
  40.     }
  41. public:
  42.     void recoverTree(TreeNode* root) {
  43.         wrongNode1 = nullptr;
  44.         wrongNode2 = nullptr;
  45.         pre = new TreeNode(INT_MIN);
  46.         // 中序遍历，寻找两个错位节点
  47.         inOederFindWrongNodes(root);
  48.         // 交换两个错为节点的值
  49.         int temp = wrongNode1->val;
  50.         wrongNode1->val = wrongNode2->val;
  51.         wrongNode2->val = temp;
  52.     }
  53. };

复杂度分析：设二叉搜索树的节点数为 N

  • 时间复杂度 O(N)：中序遍历二叉树所有节点
  • 空间复杂度 O(log N)：递归栈深度 = 二叉树深度

执行结果：

  1. 执行结果：通过
  3. 执行用时：32 ms, 在所有 C++ 提交中击败了 41.09% 的用户
  4. 内存消耗：56.2 MB, 在所有 C++ 提交中击败了 88.90% 的用户

解法二：Morris 遍历，空间复杂度 O(1)

本题的进阶要求空间复杂度 O(1)，因此需要使用 Morris 遍历