【每日算法Day 73】学妹大半夜私聊我有空吗,然后竟然做出这种事!

竟然甩给我一道算法题做,太可恶了嘤嘤嘤。

题目链接

LeetCode 99. 恢复二叉搜索树[1]

题目描述

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

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

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

题解

先不考虑空间复杂度,因为二叉搜索树的中序遍历是单调递增的,所以我们只需要求出它的中序遍历。然后两个结点被调换过位置,等价于递增序列中两个数调换了位置。那么我们只需要找出序列中第一个逆序对(前一个数)和最后一个逆序对(后一个数)就行了,然后换回它俩的位置。

但是中序遍历无论使用递归实现还是栈实现,空间复杂度都是树的高度,不是常数。

想一下为什么我们需要用递归或者栈来实现中序遍历?因为从根结点开始进入左子树之后,遍历完了左子树还需要回到根结点,然后再进入右子树继续遍历。但是如果你没有栈,你就没法从左子树回到根结点了,因为左子树中没有结点能指到根结点。

我们需要解决的就是这个问题,这里我们引入 Morris 遍历算法

下图是一个二叉搜索树例子:

v2-182884d64c3aea326bfe7814cafa3d0e_b.jpg


我们用递归来做中序遍历,访问结点的顺序是 4212346567 (这个序列就是 Morris 遍历得到的序列)。注意到非叶子结点 246 会被访问两次,第一次是作为根结点进入左子树,第二次是递归返回了,中序遍历到自己了。

那么不用递归或者栈,我们怎么在第二次成功返回根结点呢?注意到叶子结点的左右儿子都是空的,所以可以利用它们来指向根结点。

用结点 4 举个例子。首先访问 4 ,然后遍历它的左子树。左子树的最后一个遍历的结点是 3 ,那么我们就把 3 的右儿子指向根结点 4 。这样遍历完左子树之后,还能通过 3 的右儿子回到根结点 4 ,接着继续遍历右子树。

所以在第一次访问根结点时,首先要找出它左子树中最右边的那个叶子结点,把它的右儿子指向根结点。然后才能放心地递归遍历左子树,不用担心回不去啦。

具体实现的时候还有一些细节,看代码更好理解,我都写在注释里面了。

代码

c++

        /**  * Definition for a binary tree node.  * struct TreeNode {  * int val;  * TreeNode *left;  * TreeNode *right;  * TreeNode(int x) : val(x), left(NULL), right(NULL) {}  * };  */
class Solution {
public:
    void recoverTree(TreeNode* root) {
        TreeNode *x = NULL, *y = NULL, *pre = NULL, *rightmost = NULL;
        while (root) {
            // 如果有左子树,就递归遍历左子树。             if (root->left) {
                rightmost = root->left;
                // 找出左子树的最右边一个叶子结点                 while (rightmost->right && rightmost->right != root) {
                    rightmost = rightmost->right;
                }
                // 如果左子树最右边的叶子结点的右儿子是空的,                 // 那就说明根结点是第一次访问,那么就把它的右儿子指向根结点。                 // 然后递归遍历左子树。                 if (rightmost->right != root) {
                    rightmost->right = root;
                    root = root->left;
                // 否则的话说明根结点是第二次访问了,                 // 那就说明左子树已经递归完毕了,                 // 那么就判断一下是否存在逆序对。                 // 记得把左子树最右叶子结点的右儿子改回空指针。                 // 然后递归遍历右子树了。                 } else {
                    if (pre && pre->val > root->val) {
                        if (x == NULL) x = pre;
                        y = root;
                    }
                    rightmost->right = NULL;
                    pre = root;
                    root = root->right;
                }
            // 如果没有左子树,那就直接遍历右子树,同时判断是否存在逆序对。             } else {
                if (pre && pre->val > root->val) {
                    if (x == NULL) x = pre;
                    y = root;
                }
                pre = root;
                root = root->right;
            }
        }
        swap(x->val, y->val);
    }
};

      

参考资料

[1]

LeetCode 99. 恢复二叉搜索树: leetcode-cn.com/problem

算法码上来 文章被收录于专栏

公众号「算法码上来」。godweiyang带你学习算法,不管是编程算法,还是深度学习、自然语言处理算法都一网打尽,更有各种计算机新鲜知识和你分享。别急,算法码上来。

全部评论

相关推荐

粗心的雪碧不放弃:纯学历问题,我这几个月也是一直优化自己的简历,后来发现优化到我自己都觉得牛逼的时候,发现面试数量也没有提升,真就纯学历问题
点赞 评论 收藏
分享
10-29 15:38
门头沟学院 Java
榕城小榕树:难道你简历里写了配送路径优化算法?
点赞 评论 收藏
分享
最近又搬回宿舍了,在工位坐不住,写一写秋招起伏不断的心态变化,也算对自己心态的一些思考表演式学习从开始为实习准备的时候就特别焦虑,楼主一开始选择的是cpp后端,但是24届这个方向已经炸了,同时自己又因为本科非92且非科班,所以感到机会更加迷茫。在某天晚上用java写出hello world并失眠一整晚后选择老本行干嵌入式。理想是美好的,现实情况是每天忙但又没有实质性进展,总是在配环境,调工具,顺带还要推科研。而这时候才发现自己一直在表演式学习,徘徊在设想如何展开工作的循环里,导致没有实质性进展。现在看来当时如果把精力专注在动手写而不是两只手端着看教程,基本功或许不会那么差。实习的焦虑5月,楼主...
耶比:哲学上有一个问题,玛丽的房间:玛丽知道眼睛识别色彩的原理知道各种颜色,但是她生活在黑白的房间里,直到有一天玛丽的房门打开了她亲眼看到了颜色,才知道什么是色彩。我现在最大可能的减少对非工作事情的思考,如果有一件事困扰了我, 能解决的我就直接做(去哪里或者和谁吵架等等……),解决不了的我就不想了,每一天都是最年轻的一天,珍惜今天吧
投递比亚迪等公司10个岗位 > 秋招被确诊为…… 牛客创作赏金赛
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务