面试算法53:二叉搜索树的下一个节点

题目

给定一棵二叉搜索树和它的一个节点p,请找出按中序遍历的顺序该节点p的下一个节点。假设二叉搜索树中节点的值都是唯一的。例如,在图8.9的二叉搜索树中,节点8的下一个节点是节点9,节点11的下一个节点是null。
在这里插入图片描述

分析:时间复杂度O(n)的解法

解决这个问题的最直观的思路就是采用二叉树的中序遍历。可以用一个布尔变量found来记录已经遍历到节点p。该变量初始化为false,遍历到节点p就将它设为true。在这个变量变成true之后遍历到的第1个节点就是要找的节点。

解:时间复杂度O(n)的解法

public class Test {
    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);

        node4.left = node2;
        node4.right = node5;
        node2.left = node1;
        node2.right = node3;
        node5.right = node6;

        TreeNode result = inorderSuccessor(node4, node5);
        System.out.println(result);
    }

    public static TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        Stack<TreeNode> stack = new Stack<>();

        TreeNode cur = root;
        boolean found = false;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }

            cur = stack.pop();
            if (found) {
                break;
            }
            else if (p == cur) {
                found = true;
            }

            cur = cur.right;
        }

        return cur;
    }
}

分析: 时间复杂度O(h)的解法

下面按照在二叉搜索树中根据节点的值查找节点的思路来分析。从根节点开始,每到达一个节点就比较根节点的值和节点p的值。如果当前节点的值小于或等于节点p的值,那么节点p的下一个节点应该在它的右子树。如果当前节点的值大于节点p的值,那么当前节点有可能是它的下一个节点。此时当前节点的值比节点p的值大,但节点p的下一个节点是所有比它大的节点中值最小的一个,因此接下来前往当前节点的左子树,确定是否能找到值更小但仍然大于节点p的值的节点。重复这样的比较,直至找到最后一个大于节点p的值的节点,就是节点p的下一个节点。

解:时间复杂度O(h)的解法

public class Test {
    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);

        node4.left = node2;
        node4.right = node5;
        node2.left = node1;
        node2.right = node3;
        node5.right = node6;

        TreeNode result = inorderSuccessor(node4, node5);
        System.out.println(result);
    }

    public static TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode cur = root;
        TreeNode result = null;
        while (cur != null) {
            if (cur.val > p.val) {
                result = cur;
                cur = cur.left;
            }
            else {
                cur = cur.right;
            }
        }

        return result;
    }
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

memtest86 prosite v10.6

passmark官方的memtest86 v10开始支持颗粒级别的坏内存芯片定位了&#xff0c;对于特定的若干种CPU和芯片组的组合&#xff0c;支持这项功能。 当然支持颗粒定位的site版本售价4800美金&#xff0c;是比较贵的。所以网络上出现了破解版的&#xff0c;人才真是。但是鼓励大家支…

短视频矩阵营销系统工具如何助力商家企业获客?

1.批量剪辑技术研发 做的数学建模算法&#xff0c;数学阶乘的组合乘组形式&#xff0c;采用两套查重机制&#xff0c;一套针对素材进行查重抽帧素材&#xff0c;一套针对成片进行抽帧素材打分制度查重&#xff0c;自动滤重计入打分。 2.账号矩阵分发开发 多平台&#xff0c;…

【QT】QFileInfo文件信息读取

基于上节&#xff1a;【QT】文件读写-CSDN博客 //文件信息类QFileInfo info(filePath);qDebug() << "后缀名:" << info.suffix() << "大小:"<< info.size()<< "文件名:" << info.fileName() << "…

k8s:endpoint

在 Kubernetes 中&#xff0c;Endpoint 是一种 API 对象&#xff0c;它用于表示集群内某个 Service 的具体网络地址。换句话说&#xff0c;它连接到一组由 Service 选择的 Pod&#xff0c;从而使它们能够提供服务。每个 Endpoint 对象都与相应的 Service 对象具有相同的名称&am…

虹科干货 | 手把手教你通过CODESYS V3进行PLC编程(一)

文章来源&#xff1a;虹科工业控制团队 阅读原文&#xff1a;https://mp.weixin.qq.com/s/5gDXPulm8qz075H6lEmGWg 教程背景 虹科MC系列模块化控制器是基于Raspberry Pi的高性能4核控制器&#xff0c;运动控制循环时间最快可达500微秒&#xff0c;实现了计算能力和成本之间的…

【rust/esp32】初识slint ui框架并在st7789 lcd上显示

文章目录 说在前面关于slint关于no-std关于dma准备工作相关依赖代码结果参考 说在前面 esp32版本&#xff1a;s3运行环境&#xff1a;no-std开发环境&#xff1a;wsl2LCD模块&#xff1a;ST7789V2 240*280 LCDSlint版本&#xff1a;master分支github地址&#xff1a;这里 关于s…

MySQL - Zero date value prohibited

问题: timestamp字段报Caused by: com.mysql.cj.exceptions.DataReadException: Zero date value prohibited 原因: timestamp字段存入了0值, 超出了最小值1900-01-01 00:00:00, 转Java对象的时候报错 解决: 1.修复或删除原数据 2. mysqlurl 中添加zeroDateTimeBehaviorconve…

云计算的思想、突破、产业实践

文章目录 &#x1f4d5;我是廖志伟&#xff0c;一名Java开发工程师、Java领域优质创作者、CSDN博客专家、51CTO专家博主、阿里云专家博主、清华大学出版社签约作者、产品软文创造者、技术文章评审老师、问卷调查设计师、个人社区创始人、开源项目贡献者。&#x1f30e;跑过十五…

02 线性组合、张成的空间与基

线性组合、张成的空间与基 基向量缩放向量并相加给定向量张成的空间线性相关与线性无关空间的基 这是关于3Blue1Brown "线性代数的本质"的学习笔记。 基向量 当看到一对描述向量的数时&#xff0c;比如[3,-2]时&#xff0c;把这对数中的每个数&#xff08;坐标&…

New Maven Project

下面两个目录丢失了&#xff1a; src/main/java(missing) src/test/java(missing) 换个JRE就可以跑出来了 变更目录

Leetcode实战

我们今天来利用这段时间的学习实操下我们的oj题。 int removeElement(int* nums, int numsSize, int val){int dst0;int src0;while(src<numsSize){if(nums[src]!val){nums[dst]nums[src];}elsesrc;}return dst;}我们这里用用两个下标&#xff0c;src来移动&#xff0c;如果…

Spring | Sring Task (定时任务框架) 、微信小程序开发

目录&#xff1a; 一、Sring Task (定时任务框架) &#xff1a;Sring Task介绍Spring Task应用场景corn表达式corn表达式在线生成器SpringTask入门案例&#xff1a;导入maven依赖启动类上添加 EnableScheduling 注解定时方法上添加 Scheduled( cron “xxxxx” ) 注解自定义“定…

【蓝桥每日一题]-倍增(保姆级教程 篇1)

今天讲一下倍增 目录 题目&#xff1a;忠诚 思路&#xff1a; 题目&#xff1a;国旗计划 思路&#xff1a; 查询迭代类倍增&#xff1a; 本质是一个一个选区间使总长度达到 M,类似凑一个数。而我们会经常用不大于它最大的二的次幂&#xff0c;减去之后&#xff0c;再重复这…

ubuntu22.04安装公司安全VPN的方案

公司为了安全设置VPN,但是liunxVPN工具不好用&#xff0c;今天找了一个好用的VPN工具 https://www.leagsoft.com/doc/article/103107.html 有各种版本&#xff0c;支持IOS和android等系统。 安装步骤 1/下载安装程序 https://www.leagsoft.com/doc/article/103107.html 2 …

vim三种模式,文本操作(操作字符/光标,列出行号可视化块模式/多文件查看)

目录 vim--文本编辑器 功能 基本概念 命令/默认模式 插入模式 底行模式 文本操作 引入 移动光标位置 删除字符 -- x/dd 复制/粘贴字符 -- yw/yyp 替换文本 -- r / %s 底行模式 全局替换 -- /g 撤销操作 -- u / ctrlr 修改字符 -- cw 示例 跳行 -- ctrlg 底行…

Vue的虚拟dom和diff算法

一、是什么 diff算法是一种通过同层级的树节点进行比较的高效算法 diff算法是为了进行精细化比对&#xff0c;最小量更新的 特点&#xff1a; 1.同级比较&#xff1a;比较只在同层级进行 2.首尾指针法&#xff1a;从两边向组件比较 比较方式/策略&#xff1a;深度优先&#xff…

家政APP开发服务同城预约维修接单管理系统软件小程序

家政服务小程序是一个基于移动端的家政服务平台&#xff0c;为用户提供方便快捷的家政服务。以下是小程序的主要功能&#xff1a; 1. 家政服务内容展示&#xff1a;商家可以在小程序中展示各种家政服务项目&#xff0c;如清洁、保洁、保姆、月嫂、钟点工等。用户可以浏览服务信…

Ubuntu下安装vscode,并解决终端打不开vscode的问题

Visual Studio Code安装 1&#xff0c;使用 apt 安装 Visual Studio Code 在官方的微软 Apt 源仓库中可用。按照下面的步骤进行即可&#xff1a; 以 sudo 用户身份运行下面的命令&#xff0c;更新软件包索引&#xff0c;并且安装依赖软件&#xff1a; sudo apt update sud…

[自定义 Vue 组件] 小尾巴下拉菜单组件(2.0) TailDropDown

文章归档&#xff1a;https://www.yuque.com/u27599042/coding_star/kcoem6dgyn8drglb [自定义 Vue 组件] 下拉菜单(1.0) DropDownMenu&#xff1a;https://www.yuque.com/u27599042/coding_star/llltv52tchmatwg4 组件效果示例 组件所依赖的常量 在 src 目录下&#xff0c;创…

Redis中Hash类型的命令

目录 哈希类型的命令 hset hget hexists hdel hkeys hvals hgetall hmget hlen hsetnx hincrby hincrbyfloat 内部编码 Hash类型的应用场景 作为缓存 哈希类型和关系型数据库的两点不同之处 缓存方式对比 Redis自身已经是键值对的结构了,Redis自身的键值对就…