文档章节

99. Recover Binary Search Tree

cofama
 cofama
发布于 2017/05/13 22:25
字数 867
阅读 3
收藏 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
由前序和中序遍历序列重建二叉树

http://acm.nyist.net/JudgeOnline/problem.php?pid=221 输入 The input will contain one or more test cases. Each test case consists of one line containing two strings preord and i......

阿豪boy
2017/02/24
0
0
Leetcode 669. Trim a Binary Search Tree

题目链接 https://leetcode.com/problems/trim-a-binary-search-tree/description/ 题目描述 Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree......

xgnming
09/06
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 700. Search in a Binary Search Tree

文章作者:Tyan 博客:noahsnail.com | CSDN | 简书 1. Description 2. Solution Iterative Recursive Reference https://leetcode.com/problems/search-in-a-binary-search-tree/descriptio......

SnailTyan
08/07
0
0

没有更多内容

加载失败,请刷新页面

加载更多

72.告警系统邮件引擎 运行告警系统

20.23/20.24/20.25 告警系统邮件引擎 20.26 运行告警系统 20.23/20.24/20.25 告警系统邮件引擎 邮件首先要有一个mail.py,以下。 因为我们之前zabbix的时候做过,就可以直接拷贝过来 mail.s...

王鑫linux
44分钟前
1
0
09-利用思维导图梳理JavaSE-

09-利用思维导图梳理JavaSE-Java IO流 主要内容 1.Java IO概述 1.1.定义 1.2.输入流 - InputStream 1.3.输出流 - OutputStream 1.4.IO流的分类 1.5.字符流和字节流 2.InputStream类 2.1.File...

飞鱼说编程
50分钟前
3
0
Spring Cloud 微服务的那点事

在详细的了解SpringCloud中所使用的各个组件之前,我们先了解下微服务框架的前世今生。 单体架构 在网站开发的前期,项目面临的流量相对较少,单一应用可以实现我们所需要的功能,从而减少开...

我是你大哥
59分钟前
2
0
步步深入MySQL:架构->查询执行流程->SQL解析顺序

一、前言 一直是想知道一条SQL语句是怎么被执行的,它执行的顺序是怎样的,然后查看总结各方资料,就有了下面这一篇博文了。 本文将从MySQL总体架构--->查询执行流程--->语句执行顺序来探讨一...

Java干货分享
今天
1
0
gson1.7.1线程并发导致空指针问题

java.lang.NullPointerExceptionat com.google.gson.FieldAttributes.getAnnotationFromArray(FieldAttributes.java:231)at com.google.gson.FieldAttributes.getAnnotation(FieldAttribut......

东风125
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部