二叉搜索树（困难题）

二叉搜索树

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的
二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为
二叉排序树。二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势；所以应用十分广泛，例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。

对二叉搜索树进行中序遍历的时候访问到的元素是从小到大顺序排列的

二叉搜索树中的两个节点被错误地交换。

请在不改变其结构的情况下，恢复这棵树。

示例 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) 空间复杂度的解法很容易实现。
你能想出一个只使用常数空间的解决方案吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/recover-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

别人的写法

    // 中序遍历过程中，记录错误两个错误排序节点，最后进行交换
    /*
    中序遍历过程中，记录错误两个错误排序节点，最后进行交换
    只需要中序遍历一遍就可以了

    首先我们来看中序遍历过程模板
    public void inorder(TreeNode root){
            if (root == null) return ;    //终止条件
            inorder(root.left);           //访问左子树
            对当前节点进行一些操作          //访问根节点-----在遍历过程中希望实现的操作
            inorder(root.right);          //访问右子树
        }

    另一方面我们知道 对二叉搜索树进行 中序遍历的时候 访问到的元素是从小到大顺序排列的
    如我们对实例 2 恢复好的树 进行中序遍历 得到的应该是  1 2 3 4

    那这道题我们就有了大致思路
    我们对错误的二叉树进行 中序遍历 那我们按顺序访问到的数应该是按顺序排列的
    那如果对两个节点交换了顺序  那一定有两个地方是  不满足  前一个元素 < 当前元素 < 后一个元素
     如示例2      3，  1，  4， null， null， 2：
                 中序遍历结果是：1，3，2，4
                  3  这个节点不满足      2 这个节点不满足
                 所以我们使用两个全局变量在遍历过程中记录这两个节点 最后对他们进行交换
     */
class Solution {
    TreeNode t1, t2, pre;
    public void recoverTree(TreeNode root) {
        inorder(root);
        int temp = t1.val;
        t1.val = t2.val;
        t2.val = temp;
    }
    public void inorder(TreeNode root){
        if (root == null) return ;
        inorder(root.left);
        if (pre != null && pre.val > root.val) {
            if (t1 == null) t1 = pre;
            t2 = root;
        }
        pre = root;
        inorder(root.right);
    }
}

赏

谢谢你请我吃糖果

微信