剑指Offer——8.二叉树的下一个节点_BlackMaBa的博客-程序员宅基地

技术标签: 剑指Offer  二叉树  

题目:

给定一颗二叉树和其中一个节点,如何找出中序遍历序列的下一个节点?树中的节点除了有两个分别指向左、右子节点的指针,还有一个指向父节点的指针。二叉树节点定义如下:

    class BinaryTreeNode {
        int data;
        BinaryTreeNode left;
        BinaryTreeNode right;
        BinaryTreeNode parent;
	
        BinaryTreeNode(int data) {
		    this.data = data;
	    }
    }

算法思想:

1.如果该节点有右子树,那么它的下一个节点就是它的右子树的左子节点。

2.如果该节点没有右子树,并且是它的父节点的左子节点,那么它的下一个节点就是它的父节点。

3..如果该节点没有右子树,并且是它的父节点的右子节点,那么它的下一个节点就是它的第一个有左子节点的祖先节点(不包含父节点);否则没有下一个节点。

代码实现:

    public BinaryTreeNode getNext(BinaryTreeNode pNode) {
        if(pNode == null) 
            return null;
        
        if(pNode.right != null) {    //节点有右子树
            BinaryTreeNode node = pNode.right;    //得到右子节点
            while(node.left != null)     
                node = node.left;
            return node;
        } else {    //节点没有右子树
            while (pNode.parent != null) {
                BinaryTreeNode node = pNode.parent;    //得到父节点
                if (node.left == pNode)    //该节点是父节点的左子节点
                    return node;
                pNode = pNode.parent;    //得到父节点的父节点
            }
        }
        
        return null;
    }

 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/BlackMaBa/article/details/81459445

智能推荐

Android的LinearLayout.getLayoutParams().width 和 LinearLayout.getWidth() 的区别_hehehe_anzhuo的博客-程序员宅基地_layout.getlayoutparams().width = screenwidth; getw

LinearLayout.getLayoutParams().width 和 LinearLayout.getWidth() 有什么区别呢?LinearLayout.getLayoutParams().width 对应xml的 layout_width LinearLayout.getWidth() 这个东西要在 onMeasure之后才会真正的值 而onMeasure 是根据

gsoap入门学习笔记(二)---gsoap编程简述以及discover的实现_中華田園犬的博客-程序员宅基地_gsoap编程

这篇主要是对gsoap编程的一个简单介绍,以及消息结构的简单那剖析,最后简单介绍了一下discover的实现。(三)gsoap编程简述    这一部分只是对gsoap最基本的框架做个简单的介绍,并不是这部分不重要,这部分很重要,而是这部分很重要,要想使用gsoap工具进行编程,学习和研究soapdoc2.pdf文件时必须的。         1、服务器端的基本构架

是什么让我节省了60%的编码时间?在SpringBoot中使用MyBatisGenerator_万猫学社的博客-程序员宅基地

业务需求不断变更,数据库表结构不断修改,是我们逃不出的宿命。工欲善其事,必先利其器,是时候祭出神器了!

【原创】CentOS7 静默安装Oracle11g(亲测)_IT猿人的博客-程序员宅基地_centos7静默安装oracle11g

前言:我自己根据网上的帖子尝试静默安装Oracle11g失败了很多次,所以将自己最终测试成功的步骤写下来,希望可以帮助到更多的人。文章目录一、系统环境二、安装前的准备1、关闭SeLinux2、关闭防火墙3、安装依赖包、其他工具包4、检测是否31个包都有安装5、创建用户、用户组6、修改内核参数7、修改用户限制8、修改/etc/pam.d/login 文件9、修改/etc/profile 文件10、...

swustoj289消灭老鼠-利用队列解决简单的约瑟夫环_better*的博客-程序员宅基地

*289: 程序设计C 实验三 题目九 消灭老鼠题目描述有一只狡猾的老鼠,在一个环形的田埂上挖了n个老鼠洞,这些洞也是连接为一个环状,我们要用泥土填满这些鼠洞,老鼠从第0号洞开始出现(第0号洞不填),然后依次按每间隔m个洞出现一次。我们要跟在老鼠后面,当老鼠出现后填补上刚刚出现的洞。我们需要计算出老鼠最后出现那个洞(即剩下最后一个洞没有被我们填上时,这个洞的序号)。输入输入的第一行为了两个...

随便推点

PHP函数 mysql_real_escape_string 与 addslashes 的区别_weixin_34138521的博客-程序员宅基地

addslashes和mysql_real_escape_string都是为了使数据安全的插入到数据库中而进行的过滤,那么这两个函数到底是有什么区别呢?首先,我们还是从PHP手册入手:手册上addslashes转义的字符是单引号(')、双引号(")、反斜线(\)与NUL(NULL 字符)。mysql_real_escape_string转义的字符并没有被提到,只是说了一句...

android 解析org.json.JSONObject 判断Null_Misters_Chen的博客-程序员宅基地

JSONObject obj = new JSONObject("{"性别":null}");if (obj.isNull("性别")) { String xb="马德,这人居然没性别,热了狗";}

自定义属性时TypedArray的使用方法_Hily_ice的博客-程序员宅基地_import typedarray引用

有时候android传统的页面布局不足以满足我们的需求,常常需要自己定义view,通常继承View,然后重写构造方法以及onDraw等函数,再具体实现自己定义的复杂view。我们知道在给控件赋属性时,通常使用的是android系统自带的属性,比如 android:layout_height="wrap_content",除此之外,我们亦可以自己定义属性,这样在使用的时候我们就可以使用形如

ORACLE EBS AP发票到付款的数据流_夏日青草的博客-程序员宅基地

--1.发票创建时生成数据如下表--发票主表SELECT * FROM AP_INVOICES_ALL A WHERE A.INVOICE_NUM = '20111213001';--发票分配表SELECT * FROM AP_INVOICE_DISTRIBUTIONS_ALL B WHERE B.INVOICE_ID = 697444;--发票付款计划表SELECT * FROM A

MapServer和GeoServer对比_weixin_30325971的博客-程序员宅基地

https://blog.csdn.net/theonegis/article/details/45823099转载于:https://www.cnblogs.com/2008nmj/p/10456801.html

Spring动态定时器_学无止境@#$%^的博客-程序员宅基地_spring 动态定时器

大多数定时任务还是写在.xml配置里面的,这样写的最大缺点就是如果因为公司需要把定时任务执行的时间、或者是执行类更换,就需要修改.xml代码并重新提交发布版本才行。为此出了一种关联数据库动态设置定时任务技术,并可通过业务逻辑修改定时任务。 1. 我们需要在父项目的pom.xml文件中加入jar依赖:<dependency><!--定时器--> <...

推荐文章

热门文章

相关标签