文档章节

99. Recover Binary Search Tree

cofama
 cofama
发布于 2017/05/13 22:25
字数 867
阅读 3
收藏 0
点赞 0
评论 0

原题链接

Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure. Note: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

解题的关键是找到两个错误的节点。由于是二分搜索树,可以比较节点与其父节点或子节点的大小关系,来判断是否有问题。可是,即使找到了某个节点与其子节点的大小关系不符合BST的要求,还要进一步确认到底是该节点有问题还是子节点有问题,就比较麻烦了。所以从树结构中去找是比较麻烦的。BST有一个特性,就是用中序遍历输出节点的话,是一个递增的序列,所以我们可以把树“线性化”再来观察。假如一个BST用中序遍历输出123456,交换3、5节点变成125436,可以观察到,必然形成的局面是,第一个出现的交换节点一定比它的后一个节点大,第二个出现的交换节点一定比它的前一个节点小。

因此,我们可以在中序遍历时用一个变量跟踪前一个输出的节点,当第一次出现前一个节点比当前节点大的情况时,前一个节点就是交换节点;当第二次出现这种情况时,当前节点是交换节点。问题是,一般的中序遍历是递归实现,空间复杂度最坏是O(n),最好也要O(lgn),不符合题目O(1)的要求。我从网上找了下,要实现O(1)的中序遍历只能用Morris Traversal,其实就是线索二叉树的方法。

中序遍历之所以常用递归,是因为遍历完左子树后要回溯到根节点。当一个节点有左子树时,中序遍历输出时它的前一个节点(即前驱节点)是左子树的“最右节点”,通俗点讲就是“右下角”。由于右下角的右子树一定是空的(不然它就不是右下角了),所以可以把它的右指针指向根节点,这样在遍历时就可以回溯到根节点了。为了不改变树的结构,回到根节点后,还要在找到这个右下角,把它的右指针重新赋为空。

class Solution {
public:
    void recoverTree(TreeNode* root) {
        TreeNode* prev = NULL;
        TreeNode* tmp = NULL;
        TreeNode* first = NULL;
        TreeNode* second = NULL;
        while(root!=NULL) {
            if(root->left!=NULL) {
                tmp = root->left;
                while(tmp->right!=NULL && tmp->right!=root) tmp = tmp->right;
                if(tmp->right==NULL) {
                    tmp->right = root;
                    root = root->left;
                }
                else {
                    tmp->right = NULL;
                    //find wrong elements
                    if(first==NULL && prev->val>root->val) first = prev;
                    if(first!=NULL && prev->val>root->val) second = root;
                    prev = root;
                    //end finding
                    root = root->right;
                }
            }
            else {
                //find wrong elements
                if(first==NULL && prev!=NULL && prev->val>root->val) first = prev;
                if(first!=NULL && prev->val>root->val) second = root;
                prev = root;
                //end finding
                root = root->right;
            }
        }
        //swap
        int temp = first->val;
        first->val = second->val;
        second->val = temp;
    }
};

代码中,first、second记录两个交换的节点,prev跟踪前一个遍历的节点。如果当前节点有左子树,在开始左子树遍历前,都要先找到它的前驱节点。如果前驱节点的右指针已经指向当前节点了,说明左子树已经遍历完了,可以处理当前节点并遍历右子树。因为中序遍历是按“左中右”的顺序,所以改变前驱节点的右指针也是符合遍历习惯的。

© 著作权归作者所有

共有 人打赏支持
cofama
粉丝 0
博文 24
码字总数 19162
作品 0
广州
程序员
LeetCode Question Difficulty Distribution 问题难度和频率分布

Leetcode问题难度和频率分布表 引用自: https://zephyrusara.blogspot.jp/2014/07/leetcode-question-difficulty.html LeetCode Question Difficulty Distribution : Sheet1......

xidiancoder
2017/09/10
0
0
ZOJ Problem Set - 1944 Tree Recovery(二叉树三种遍历知二求三)

Tree Recovery Time Limit: 2 Seconds Memory Limit: 65536 KB Little Valentine liked playing with binary trees very much. Her favorite game was constructing randomly looking binary......

hushhw
2017/11/27
0
0
Leetcode——二叉树常考算法整理

二叉树常考算法整理 希望通过写下来自己学习历程的方式帮助自己加深对知识的理解,也帮助其他人更好地学习,少走弯路。也欢迎大家来给我的Github的Leetcode算法项目点star呀~~ 前言 二叉树即...

qq_32690999
05/28
0
0
二叉搜索树的简明实现(ES5 & ES6)

二叉树 & 二叉搜索树 二叉树(Binary Tree)是 n(n >= 0)个节点的有限集合,集合为空集时,叫作空二叉树;不为空时,由根节点及左子树、右子树组成,左子树、右子树也都是二叉树。 从这个描...

天方夜
07/04
0
0
[LeetCode] Serialize and Deserialize BST 二叉搜索树的序列化和去序列化

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a networ......

机器的心脏
2017/12/10
0
0
验证二叉搜索树

原题   Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows:   The left subtree of a node contains only nodes with k......

一贱书生
2016/12/20
0
0
浅谈二分查找

定义 In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value ......

云胡_
2017/11/26
0
0
[LeetCode] Trim a Binary Search Tree 修剪一棵二叉搜索树

Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in [L, R] (R >= L). You might need to change the root of......

机器的心脏
2017/12/06
0
0
Trim a Binary Search Tree

问题: Given a binary search tree and the lowest and highest boundaries as and , trim the tree so that all its elements lies in (R >= L). You might need to change the root of th......

叶枫啦啦
01/14
0
0
判断一棵树是否为二叉搜索树 Validate Binary Search Tree

问题: Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys les......

叶枫啦啦
2017/09/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

JPA @MappedSuperclass 注解说明

基于代码复用和模型分离的思想,在项目开发中使用JPA的@MappedSuperclass注解将实体类的多个属性分别封装到不同的非实体类中。 1.@MappedSuperclass注解只能标准在类上:@Target({java.lang....

海博1600
6分钟前
0
0
Scala Configuration 相关API

Play使用了 Typesafe config library,但是也提供了一个有着更多Scala高级特性的的 Configuration 封装。不熟悉Typesafe配置的开发者可以移步 configuration文件的语法和特性文档。 读取配置...

Landas
今天
1
0
使用cookie技术 记住账号

1. 效果 2. 实现过程 2.1 前端 将用户的选中传递给后台 这个参数的获取是 参考:https://my.oschina.net/springMVCAndspring/blog/1860498 // var rememberLogin = $("#rememberLoginId").i...

Lucky_Me
今天
1
0
《趣谈网络协议》02之网络分层的真实含义

一、提出问题 1.提出问题 当你听到什么二层设备、三层设备、四层 LB 和七层 LB 中层的时候,是否有点一头雾水,不知道这些所谓的层,对应的各种协议具体要做什么“工作”? 2.这四个问题你弄...

aibinxiao
今天
2
0
Python3学习日志二 Python中的集合set和字典dict

1.集合set 定义一个集合set 我们可以看到定义集合set有两种不同的形式,如果要定义一个空的集合set不能用{}而是要用set();另外,集合是无序的,而且set中的元素是不可重复的,如果你定义了一...

Mr_bullshit
今天
0
0
adb 操作指令详解

ADB,即 Android Debug Bridge,它是 Android 开发/测试人员不可替代的强大工具,也是 Android 设备玩家的好玩具。 注:有部分命令的支持情况可能与 Android 系统版本及定制 ROM 的实现有关。...

孟飞阳
今天
0
0
nodejs安装以及环境配置(很好的node安装和配置文章,少走很多弯路)

一、安装环境 1、本机系统:Windows 10 Pro(64位) 2、Node.js:v6.9.2LTS(64位) 二、安装Node.js步骤 1、下载对应你系统的Node.js版本:https://nodejs.org/en/download/ 2、选安装目录进...

sprouting
今天
1
0
Redisson

了解了Redisson,发现使用挺简单的,接下来准备深入学习一下。 Redisson介绍 Redisson是架设于Redis基础之上的一个Java驻内存数据网格(In-Memory Data Grid) Redisson在基于NIO的Netty框架上...

to_ln
今天
0
0
python有哪些好玩的应用实现,用python爬虫做一个二维码生成器

python爬虫不止可以批量下载数据,还可以有很多有趣的应用,之前也发过很多,比如天气预报实时查询、cmd版的实时翻译、快速浏览论坛热门帖等等,这些都可以算是爬虫的另一个应用方向! 今天给...

python玩家
今天
0
0
python爬虫日志(3)-爬去异步加载网页

在浏览器检查元素页面中,选取Network中的XHR选项即可观察每次加载页面,网页发出的请求,观察url的规律即可利用封装的函数对每一页进行爬取。

茫羽行
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部