中序遍历查找下一个节点

el/2024/6/13 22:30:26

给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。

思路:就是只考虑当前节点的右边,父亲部分。

 

public class TreeLinkNode {int val;TreeLinkNode left = null;TreeLinkNode right = null;TreeLinkNode next = null;TreeLinkNode(int val) {this.val = val;}
}
//解题思路
//如果一个节点的右子树不为空,那么该节点的下一个节点是右子树的最左节点;// 否则,向上找第一个左链接指向的树包含该节点的祖先节点。public TreeLinkNode GetNext(TreeLinkNode pNode) {if (pNode.right != null) {TreeLinkNode node = pNode.right;while (node.left != null)node = node.left;return node;} else {while (pNode.next != null) {TreeLinkNode parent = pNode.next;if (parent.left == pNode)return parent;pNode = pNode.next;}}return null;
}

 


http://www.ngui.cc/el/5179139.html

相关文章

打印从 1 到最大的 n 位数

题目描述 输入数字 n,按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3,则打印出 1、2、3 一直到最大的 3 位数即 999。 解题思路 由于 n 可能会非常大,因此不能直接用 int 表示数字,而是用 char 数组进行存储。 使用回溯…

在 O(1) 时间内删除链表节点

解题思路 ① 如果该节点不是尾节点,那么可以直接将下一个节点的值赋给该节点,然后令该节点指向下下个节点,再删除下一个节点,时间复杂度为 O(1)。② 如果链表只有一个节点,那么直接② 否则,就需要先遍历链表…

题目描述 一个链表中包含环,请找出该链表的环的入口结点。要求不能使用额外的空间。

题目描述 一个链表中包含环,请找出该链表的环的入口结点。要求不能使用额外的空间。可以参见剑指offer上的原题。代码如下: package cn.cqu.edu;public class NodeOfLoop {class ListNode {int val;ListNode next null;ListNode(int val) {this.val v…

目标检测中mAP的定义

作者:nowgood 链接:https://www.zhihu.com/question/53405779/answer/506000532 来源:知乎 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。 目标检测中衡量识别精度的指标是mAP(mean averag…

java jdk中的动态代理和Cglib中的动态代理的解析

为什么要用动态代理? 因为静态代理需要额外编写代理类,对于每一个要代理的对象,都要书写一个额外的代理类。 使用代理的原因? 有些类是不能够直接访问的或者有些访问要经过特殊处理。 1. Java JDK中的动态代理 java jdk中的动态…

求1+2+3+4+5+..+n

题目描述 求123...n,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。 其主要思想是递归,这个程序很美。 package cn.cqu.edu;public class Sum_Solution1 {public int Sum_Solution(in…

tomcat运行java web时,报这个错:org.springframework.beans.factory.BeanCreationException

具体出错信息如下: 严重: StandardWrapper.Throwable org.springframework.beans.factory.BeanCreationException: Error creating bean with name userController: Injection of autowired dependencies failed; nested exception is org.springframework.beans.factory.Bea…

eclipse下springmvc+spring+maven+mybatis+mysql的搭建,并实现增删改查

eclipse下SpringMVC+Maven+Mybatis+MySQL项目搭建 这篇文章主要讲解在eclipse环境下SpringMVC+Maven+Mybatis+MySQL的项目搭建过程。 创建Maven工程。右击-->New->Other 点击->Manven Porject 点击->勾选快速框架 输入项目名,包(Packaging,如果只是普通的项目,…

大数据笔试面试题

问题: 有一个包含20亿个全是32位整数的大文件,在其中找到出现次数最多的数,但是内存限制只有2G. 解题思路:先将这个20亿个整数进行哈希分流,比如说分别分流到16个小文件中,然后用哈希表分别计算出每一个小…