专栏首页架构说leetcode每日一题-99. 恢复二叉搜索树

leetcode每日一题-99. 恢复二叉搜索树

一、参考代码

完成比完美更重要,自己动手写一些看

[99] 恢复二叉搜索树

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

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

  • 放轻松,虽然是c++实现,拒绝奇技淫巧,通俗易懂。
//递归遍历
class Solution {
public:
    void recoverTree(TreeNode* root)
    {
        // 01 check
        if (root == NULL) {
            return;
        }
        // 02 dfs
        TreeNode* first = NULL; //第一个元素 6>3,选择 6  【1 2 3 4 5 6】(6,2)
        TreeNode* second = NULL; // 第二个元素 5>2 选择 2 【1 2 3 4 5 6】(6,2)
        TreeNode* pre = NULL; // 记录上一个记录
        recoverTree(root, pre, first, second);

        //03 swap
        if (first && second) {
            int temp = first->val;
            first->val = second->val;
            second->val = temp;
        }
    }

    void recoverTree(TreeNode* root, TreeNode*& pre, TreeNode*& first, TreeNode*& second)
    {
        if (NULL == root) {
            return; //递归退出条件
        }
        //01 中序递归遍历
        recoverTree(root->left, pre, first, second);

        //here
        //判断是否逆序
        if (pre && pre->val > root->val) {
            if (first == NULL) {
                first = pre; //must
                second = root;
                // 【1  2  3  4 】 (2,3)
                // 【1  3  2  4 】  只有3>2 ,没有第二个比较, 该怎么办 (first>second)
            } else {
                second = root;

                // *假设有一个递增序列 a = [ 1, 2, 3, 4, 5, 6, 7 ]
                //  如果我们交换两个不相邻的数字,例如 2 和 6,
                // 原序列变成了 a = [ 1, 6, 3, 4, 5, 2, 7 ] ,
                //   first 6 > 3, second)5 > 2
            }
        }

        //记录
        pre = root;
        recoverTree(root->right, pre, first, second);
    }
};

//非递归遍历
class Solution {
public:
    //32ms
    void recoverTree(TreeNode* root)
    {

        //01 check
        if (nullptr == root)
            return;

        //02 依赖stack
        //非递归遍历,在一个函数内完成,不需要二级指针传递参数.保存改变
        TreeNode* first = nullptr;
        TreeNode* second = nullptr;
        TreeNode* pre = nullptr;
        vector<TreeNode*> stack; //用数组模拟栈
        //stack.push_back(root); 这里插入不合适

        while (stack.size() > 0 || nullptr != root) {
            //遍历左子树
            while (root) {
                stack.push_back(root);
                root = root->left; //move
            }
            // 走到这里说明 root ==nill

            //访问节点
            root = stack.back();
            stack.pop_back();
            //判断是否逆序
            if (nullptr != pre && pre->val > root->val) {
                if (nullptr == first) {
                    first = pre;
                }
                second = root;
            }
            pre = root; //下次访问

            //遍历右子树
            root = root->right;
        }
        //03 swap
        if (first && second) {
            int temp = first->val;
            first->val = second->val;
            second->val = temp;
        }
    }
};
  • golang
//递归遍历
func recoverTree(root *TreeNode) {

    if nil ==root {
        return 
    }
    //递归遍历,需要通过函数参数 修改另外一个函数的变量 
    var first  *TreeNode  =nil  //两个节点被错误.out
    var second *TreeNode  =nil  //两个节点被错误,out
    var pre   *TreeNode  =nil //一个变量空间

    InOrderTree(root,&pre,&first,&second) //golang 没用引用传递

    first.Val, second.Val = second.Val, first.Val //修改指针内容,必须二级指针
}

func InOrderTree(root *TreeNode, pre **TreeNode,first **TreeNode, second **TreeNode) {
    if nil ==root {
        return 
    }

    InOrderTree(root.Left,pre,first,second)
    //默认为ni 
    if nil != *pre  && (*pre).Val > (*root).Val {
        if  *first == nil {
               *first =*pre
        } 
           *second =root
    }

    *pre =root // 
    InOrderTree(root.Right,pre,first,second)
}

二、题目描述

检查 题目是否看明白,理解有没有偏差

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

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

示例 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
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思考 60秒 。。。

思考 60秒 。。

这个题目试着这里开始入手

算法五个重要的特征:

  • 输入项,输出项(题目已经给了)
  • 可行性(复杂问题转化成熟悉子问题)
  • 有穷性(在算法描述体现)
  • 确切性(在算法描述体现)

三、解题思路

检查 思路是否清晰合理,不是靠道听途说, 别人说这样好就好,

最迷惑地方

熟悉的子问题

步骤描述

复杂度分析

四 、 举一反三

分享最实用的经验 , 希望每一位来访的朋友都能有所收获! 如果有疑问请联系我,一起探讨,进步。

本文分享自微信公众号 - 架构说(JiaGouS),作者:王传义

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-08-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 958. 二叉树的完全性检验

    输入:[1,2,3,4,5,null,7] 输出:false 解释:值为 7 的结点没有尽可能靠向左侧

    程序员小王
  • 单链表中头节点作用(深入理解)

    今天QQ群里有人咨询一个问题 例如单链表中头节点作用 然后联想到做项目中解决core一个问题 虽然每天都在吃饭睡觉打豆豆,啥框架业务都不懂 解决了这一个...

    程序员小王
  • 关于linux进程间的close-on-exec机制

    待我们仔细分析流量已经用netstat查看具体的连接数,离我们设置的上限还差很远。这个时候开始怀疑我们的程序是不是有bug导致文件描述符泄露了。

    程序员小王
  • LeetCode 897 Increasing Order Search Tree

    给定一颗二叉搜索树,重新进行排序,使其根节点是最小值,且每个节点都没有左子树,只有一个右子树,最终还要保持该树是一颗二叉搜索树.

    一份执着✘
  • LeetCode37|两颗二叉搜索树中所有元素

    队列的使用,队列的特点是先进先出,这个特性在以往的文章中说过了,前提是理解队列的使用,需要了解的可以看下这篇文章java进阶|java队列源码分析

    后端Coder
  • Golang 多goroutine异步通知error的一种方法

    作者近期在写一个项目时遇到了这样的需求:调用一个库API函数,函数内部又会拉起若干个后台goroutine。这时后台goroutine如果遇到错误想要及时通知库...

    李海彬
  • 如何避免自己的情书被当做垃圾邮件屏蔽掉?

    “我上个月开始,打算追一个女生,坚持每天给她写一封邮件,发送一点小小的问候。可是这一个月过去了,她一封也没有回过我……我以为只是女神懒得回邮件,但是今天鼓起勇气...

    magic2728
  • 如何使用我们的telnet操作memcached

    相信我们做PHP开发的人都会用到memcached这个web缓存系统。Memcached 是一个高性能的分布式内存对象缓存系统,用于动态Web应用以减轻数据库负...

    A梦多啦A
  • linux之iptables应用详解

    --icmp-type     8:echo-request     0:echo-reply 例子:两个主机 in和out,允许in ping out ...

    用户4877748
  • 设计一个有getMin功能的栈1.设计一个有getMin功能的栈

    仇诺伊

扫码关注云+社区

领取腾讯云代金券