【面试高频题】二叉树“神级遍历“入门

题目描述

这是 LeetCode 上的 「99. 恢复二叉搜索树」 ,难度为 「中等」

Tag : 「二叉树」、「树的搜索」、「递归」、「迭代」、「中序遍历」、「Morris 遍历」

给你二叉搜索树的根节点 root,该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下,恢复这棵树 。

示例 1: alt

输入:root = [1,3,null,null,2]

输出:[3,1,null,null,2]

解释:3 不能是 1 的左孩子,因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。

示例 2: alt

输入:root = [3,1,4,null,null,2]

输出:[2,1,4,null,null,3]

解释:2 不能在 3 的右子树中,因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。

提示:

  • 树上节点的数目在范围

进阶:使用 空间复杂度的解法很容易实现。你能想出一个只使用 空间的解决方案吗?

基本分析

首先,别想复杂了。

所谓的恢复二叉树(两节点互换),只需要将两节点的 val 进行互换即可,而不需要对节点本身进行互换。

中序遍历 - 递归 & 迭代

二叉搜索树,其中序遍历是有序的。

要找到哪两个节点被互换,可通过比对中序遍历序列来实现。

但将整个中序遍历序列保存下来,再检测序列有序性的做法,复杂度是 的(不要说题目要求的 ,连 都达不到)。

所以第一步,「这个「递归 & 迭代」的次优解,我们先考虑如何做到 的空间复杂度,即在中序遍历过程中找到互换节点」

其实也很简单,除了使用 ab 来记录互换节点,额外使用变量 last 来记录当前遍历过程中的前一节点即可:

若存在前一节点 last 存在,而且满足前一节点值大于当前节点(last.val > root.val),违反“有序性”,根据是否为首次出现该情况分情况讨论:

  • 若是首次满足条件,即 a == null,此时上一节点 last 必然是两个互换节点之一,而当前 root 只能说是待定,因为有可能是 lastroot 实现互换,也有可能是 last 和后续的某个节点实现互换。

    此时有 a = last, b = root

  • 若是非首次满足条件,即 a != null,此时当前节点 root 必然是两个互换节点中的另外一个。

    此时有 b = root

综上:如果整个中序遍历的序列中“逆序对”为一对,那么互换节点为该“逆序对”的两个成员;若“逆序对”数量为两对,则互换节点为「第一对“逆序对”的首个节点」和「第二对“逆序对”的第二个节点」。

Java 代码(递归):

class Solution {
    TreeNode a = null, b = null, last = null;
    public void recoverTree(TreeNode root) {
        dfs(root);
        int val = a.val;
        a.val = b.val;
        b.val = val;
    }
    void dfs(TreeNode root) {
        if (root == nullreturn ;
        dfs(root.left);
        if (last != null && last.val > root.val) {
            if (a == null) {
                a = last; b = root;
            } else {
                b = root;
            }
        }
        last = root;
        dfs(root.right);
    }
}

Java 代码(迭代):

class Solution {
    public void recoverTree(TreeNode root) {
        Deque<TreeNode> d = new ArrayDeque<>();
        TreeNode a = null, b = null, last = null;
        while (root != null || !d.isEmpty()) {
            while (root != null) {
                d.addLast(root);
                root = root.left;
            }
            root = d.pollLast();
            if (last != null && last.val > root.val) {
                if (a == null) {
                    a = last; b = root;
                } else {
                    b = root;
                }
            }
            last = root;
            root = root.right;
        }
        int val = a.val;
        a.val = b.val;
        b.val = val;
    }
}
  • 时间复杂度:
  • 空间复杂度: ,其中 为树高

中序遍历 - Morris 遍历

Morris 遍历也就是经常说到的“神级遍历”,其本质是通过做大常数来降低空间复杂度。

还是以二叉树的中序遍历为例,无论是递归或是迭代,为了在遍历完左节点(也可以是左子树)时,仍能回到父节点,我们需要使用数据结构栈,只不过在递归做法中是用函数调用充当栈,而在迭代做法则是显式栈。

「这使得空间复杂度为 ,而 Morris 遍历的核心则是利用“路径底部节点”中的空闲指针进行线索。」

举个 🌰,对于一棵最简单的二叉树:

alt

在中序遍历过程中,如果选择递归或迭代方式,并且不使用栈的情况,当遍历完左子节点(或左子树的最后一个节点)后,将会面临无法返回根节点的问题。

在 Morris 遍历中,从根节点开始,尚未真正遍历左子节点之前,就会先建立「左子节点(或左子树的最后一个节点)」与「当前根节点」之间的链接,从而避免使用栈。

具体的,Morris 遍历的中序遍历遵循如下流程(喜欢的话可以背过):

  1. 令根节点为当前节点

  2. 只要当前节点不为空(while (root != null) ),重复执行如下流程:

    • 若当前节点的左子节点为空(root.left = null),将当前节点更新为其右子节点(root = root.right)

    • 若当前节点的左子节点不为空,利用临时变量 t 存储,找到当前节点的前驱节点(左子树中最后一个节点):

      • 若前驱节点的右子节点为空(t.right = null),将前驱节点的右子节点链接到当前节点(t.right = root),并将当前节点更新为左子节点(root = root.left

      • 若前驱节点的右子节点不为空,说明已链接到当前节点,此时将前驱节点的右子节点置空(删除链接 t.right = null),遍历当前节点,并将当前节点更新为右子节点(root = root.right

Java 代码:

class Solution {
    public void recoverTree(TreeNode root) {
        TreeNode a = null, b = null, last = null;
        while (root != null) {
            if (root.left == null) {
                if (last != null && last.val > root.val) {
                    if (a == null) {
                        a = last; b = root;
                    } else {
                        b = root;
                    }
                }
                last = root;
                root = root.right;
            } else {
                TreeNode t = root.left;
                while (t.right != null && t.right != root) t = t.right;
                if (t.right == null) { // 若前驱节点右子树为空, 说明是真正遍历左子树前, 建立与当前根节点的链接, 然后开始真正遍历左子树
                    t.right = root;
                    root = root.left;
                } else {  // 若已存在链接, 说明是第二次访问根节点, 左子树(前驱节点)已遍历完, 此时应该解开链接, 遍历当前节点以及右子树
                    t.right = null;
                    if (last != null && last.val > root.val) {
                        if (a == null) {
                            a = last; b = root;
                        } else {
                            b = root;
                        }
                    }
                    last = root;
                    root = root.right;
                }
            }
        }
        int val = a.val;
        a.val = b.val;
        b.val = val;
    }
}
  • 时间复杂度:
  • 空间复杂度:

最后

这是我们「刷穿 LeetCode」系列文章的第 No.99 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/130551.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【Hive SQL】统计同名路径下目录数量(基于reverse、split和substr函数)

首先&#xff0c;Hive事务表所产生的的路径信息如下&#xff1a; PS&#xff1a;其中路径信息格式为 /user/hive/warehouse/${database_name}.db/${table_name}/*/user/hive/warehouse/test.db/tran_ts/delete_delta_0000002_0000002_0000 /user/hive/warehouse/test.db/tran_…

【脑机接口开源数据处理包】brainflowBrainFlow是一个库,旨在获取,解析和分析脑电图,肌电图,心电图和其他类型的数据从生物传感器。

BrainFlow是一个库&#xff0c;旨在获取&#xff0c;解析和分析脑电图&#xff0c;肌电图&#xff0c;心电图和其他类型的数据从生物传感器。 brainflow开源库官网地址 [https://brainflow.readthedocs.io/en/stable/](https://brainflow.readthedocs.io/en/stable/) 它提供了…

AntDB数据库参加ACDU中国行杭州站,分享数据库运维实践与经验

关于ACDU 和中国行: ACDU是由墨天轮社区举办的中国数据库联盟的品牌活动之一&#xff0c;在线下汇集数据库领域的行业知名人士&#xff0c;共同探讨数据库前沿技术及其应用&#xff0c;促进行业发展和创新的平台&#xff0c;也为开发者们提供友好交流的机会。 AntDB作为具有技术…

Facebook 广告:如何为移动设备投放广告

图片来源于&#xff1a;SaleSmartly官网 如果您希望目标受众发现并看到您的企业&#xff0c;那么广告是至关重要的&#xff0c;但是哪些是宣传您的品牌的最佳方式呢&#xff1f;当今最常用的平台&#xff08;手机&#xff09;上的广告怎么样&#xff1f;能够回答这些问题很重要…

Postman —— HTTP请求基础组成部分

一般来说&#xff0c;所有的HTTP Request都有最基础的4个部分组成&#xff1a;URL、 Method、 Headers和body。 &#xff08;1&#xff09;Method 要选择Request的Method是很简单的&#xff0c;Postman支持所有的请求方式。 &#xff08;2&#xff09;URL 要组装一条Request…

Android获取系统读取权限

在Androidifest.xml文件中加上授权语句 <uses-permission android:name"android.permission.WRITE_EXTERNAL_STORAGE"/><uses-permission android:name"android.permission.READ_EXTERNAL_STORAGE"/>

01 PHP基础知识讲解

一 php基础知识 PHP文件的默认拓展名是“php”。 PHP文件中包含HTML标记、PHP标记、PHP代码以及空格和注释。 PHP标记&#xff1a;开始标记<?php 结束标记 ?> 中间内容是PHP代码。 PHP代码&#xff1a;学习第一个指令 echo 功能是用于输出字符串 。 语句结束符&a…

电脑更换硬盘的时候怎么迁移系统?

为什么需要迁移系统&#xff1f; 在一些关于电脑DIY或Windows相关的论坛社区中&#xff0c;有很多人发帖询问怎么迁移系统。那么这个系统迁移&#xff0c;究竟是何含义呢&#xff1f;通俗易懂地解释一下&#xff0c;就是创建一个完整无缺的操作系统复制品&#xff0c;它与系…

一文了解VR全景,VR全景有哪些优势?

引言&#xff1a; VR全景技术近年来崭露头角&#xff0c;已经成为宣传领域的一大亮点。不仅在娱乐&#xff0c;旅游行业广泛应用&#xff0c;还在商业和教育等领域崭露头角。 一&#xff0e;什么是VR全景&#xff1f; VR全景&#xff0c;全名Virtual Reality Panorama&#x…

服务器数据恢复-EVA存储多块硬盘磁头和盘片损坏离线的数据恢复案例

服务器数据恢复环境&#xff1a; HP EVA某型号存储&#xff0c;存储中一共有23块磁盘&#xff0c;上层映射给一台windows server服务器上。 服务器故障&检测&分析&#xff1a; 该EVA存储上三块硬盘指示灯显示黄色&#xff0c;此时存储设备还能正常工作。运维更换显示黄…

SLAM从入门到精通(编写第一个package)

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 前面我们安装了ROS环境&#xff0c;接着就可以开始进行ROS程序的开发了。在开发之前&#xff0c;我们有几个概念需要厘清一下。第一个是workspace&…

springboot之三:原理分析之自动配置condition

导入&#xff1a; SpringBoot是如何知道要创建哪个Bean的&#xff1f;比如Spring Boot是如何知道要创建RedisTemplate的&#xff1f; Condition&#xff1a; Condition是在Spring4.0增加的条件判断功能&#xff0c;通过这个可以实现选择性的创建Bean操作。 自定义条件&…

数仓学习之DWD学习

登录不是原子行为&#xff0c;而登录成功是&#xff0c; 而支付也不是原子&#xff0c;也分成功失败。 什么是原子型? 一条线 注意一下密码, mysql的密码是MD5加密,而MD5的长度为固定的32 1.怎么构建事务表? 1.确定表名 2.确定一行数据所表示的含义 3.确定列定义 4.确定度…

让NPU跑起来iTOP_RK3588开发板在Linux系统中使用NPU

下载 rknpu2 并拷贝到虚拟机 Ubuntu&#xff0c;如下图所示&#xff0c;RKNPU2 提供了访问 rk3588 芯片 NPU的高级接口。 下载地址为“iTOP-3588 开发板\02_【iTOP-RK3588 开发板】开发资料\12_NPU 使用配套资料\01_rknpu2 工具” 对于 RK3588 来说&#xff0c;Linux 平台 RK…

2023最新软件测试面试题大全(包含答案)

前言 在我认为&#xff0c;对于测试面试以及进阶的最佳学习方法莫过于刷题博客书籍视频总结&#xff0c;前几者博主将淋漓尽致地挥毫于这篇博客文章中&#xff0c;至于总结在于个人&#xff0c;实际上越到后面你会发现面试并不难&#xff0c;其次就是在刷题的过程中有没有去思考…

Postman接口压力测试 ---- Tests使用(断言)

所谓断言&#xff0c;主要用于测试返回的数据结果进行匹配判断&#xff0c;匹配成功返回PASS&#xff0c;失败返回FAIL。 下图方法一&#xff0c;直接点击右侧例子函数&#xff0c;会自动生成出现在左侧窗口脚本&#xff0c;只需修改数据即可。 方法二&#xff1a;直接自己写脚…

物资管理系统数据分析报告

目 录 1.需求分析 1.1系统目标与要求 1.2系统分析 1.3业务流程图 2.系统逻辑方案 2.1数据流程图&#xff08;DFD&#xff09;&#xff1a; 2.2数据字典&#xff08;简称DD&#xff09; 3系统总体结构设计 3.1软件系统总体结构设计 3.2数据存储的总体设计…

Mac端交互式原型设计 Axure RP 8 for Mac汉化

Axure RP 8是一款专业的交互原型设计工具&#xff0c;它被广泛应用于用户体验设计、界面设计和产品原型制作等领域。该软件提供了丰富的功能和工具&#xff0c;使用户能够创建出具有高度交互性和可视化效果的原型。 Axure RP 8的主要特点和功能包括&#xff1a; 1. 快速原型&a…

【广州华锐互动】智能变电站AR仿真实训系统大大提高培训的效率和质量

随着电力行业的不断发展&#xff0c;变电站的建设和运维变得越来越重要。传统的变电站运维培训方式存在着诸多问题&#xff0c;如难以真实模拟变电站运行环境、信息传递不及时、难以掌握实际操作技能等问题。而智能变电站AR仿真实训系统可以为变电站运维人员带来全新的培训方式…

023-从零搭建微服务-推送服务(三)

原【短信服务】更名【推送服务】 写在最前 如果这个项目让你有所收获&#xff0c;记得 Star 关注哦&#xff0c;这对我是非常不错的鼓励与支持。 源码地址&#xff08;后端&#xff09;&#xff1a;https://gitee.com/csps/mingyue 源码地址&#xff08;前端&#xff09;&a…