【Offer】[8] 【中序遍历的下一个结点】
2024-10-21 13:37:29
题目描述
给定一棵二叉树和其中的一个结点，如何找出中序遍历顺序的下一个结点？ 树中的结点除了有两个分别指向左右子结点的指针以外，还有一个指向父结点的指针。
思路分析
- 链表的结构中 有指向父结点的指针，方法输入为二叉树的头结点
- 分为两种情况：
- 若当前结点有右子树时，它中序遍历的下一个结点为 它的右子树中的最左子结点；
- 若当前结点没有右子树时:
- 该结点是它父结点的左子结点，那么它的下一个结点即它的父节点；
- 该结点是它父结点的右子结点，那么他的下一个结点就需要沿着它的父节点链进行搜寻，如果搜寻到 一个结点是它父结点的左子结点(复现第一种情况)，是那么下一个结点即为此结点的父结点。
Java代码
public static TreeNodeWithParent GetNext(TreeNodeWithParent tree) {
return Solution1(tree);
}
/**
*
* @param tree
* @return
*/
private static TreeNodeWithParent Solution1(TreeNodeWithParent tree) {
if (tree == null) {
return null;
}
TreeNodeWithParent p = tree;
if (p.right != null) {
p = p.right;
while (p.left != null) {
p = p.left;
}
return p;
}
while (p.parent != null) {
if (p == p.parent.left) {
return p.parent;
}
p = p.parent;
}
return null;
}
代码链接
最新文章
- 基于jQuery左右滑动切换特效 附源码
- Linux-002-执行命令时，提示： -bash: {命令}: command not found
- unity平台的预处理
- [转]Snappy压缩库安装和使用之一
- 误导人的接口（interface）
- 前谷歌首席 Java 架构师谈如何设优秀的 API
- 10.5 noip模拟试题
- vb安装过程中 ntvdm.exe[9696]中发生未处理的win32异常
- 限定只能处理"A仓"和"B仓"入库
- SQLite数据库查看工具(免费)
- Spring+SpringMVC+MyBatis深入学习及搭建(十二)——SpringMVC入门程序
- Python爬虫入门：Cookie的使用
- 基于ITextSharp插件在ASP.NET MVC中将图表导出为PDF
- ASP.NET MVC页面报错System.InvalidOperationException The view found at '~/Views/Home/Index.cshtml' was not created.
- 你不可不知的Java引用类型之——WeakReference源码详解
- Shell-2--输入输出重定向
- CS190.1x-ML_lab4_ctr_student
- 蜻蜓FM下载文件名还原
- 三.插入和查找MySQL记录 数据类型
- Python面试题之Python正则表达式re模块