黑客技术点击右侧关注，了解黑客的世界！
Java开发进阶点击右侧关注，掌握进阶之路！
Python开发点击右侧关注，探讨技术话题！
作者 | 小鹿
来源 | 小鹿动画学编程（Web_Coding）
题目
给定一棵二叉树和其中的一个的节点，如何找出中序遍历的下一节点。树中的节点除了有两个分别指向左、右子树的指针，还有一个指向父节点的指针。
如：中序遍历序列为 {d,b,h,e,i,a,f,c,g}。
问题分析
我们根据题目进行分析，要想求出其中一个树节点中序遍历的下一节点是什么，我们需要对每个单独的情况分别进行分析。
根据中序遍历的规律（先遍历左子节点，然后遍历根节点，最后遍历右子节点），下一节点可能存在的情况如下。
动画实现
情况一：如果查找的节点有右子树，则下一结点在它右子树的最左子节点。如下图中的 b 节点的下一节点为 h 节点
如果右子树没有左子节点，则下一节点为右子节点。如下图中的 c 节点的下一节点为 g 节点
情况二：如果当前节点没有右子树且是父节点的左子节点，则它的下一节点是它的父节点。如下图中的 d 节点的下一节点为 b 节点。
情况三：如果当前的节点没有右子树且是父节点的右子节点。对于这种情况，我们就一直向它的父节点遍历，直到找到第一个是父节点的左子节点的节点。如果该节点的父节点存在，则父节点就是要查找的下一节点。如下图中的 i 的下一节点为 a。
再比如没有找到这样的节点，下节点为空。如图中的 g 节点的下一结点为空。
代码实现
JavaScript
Java
Python
测试用例
- 普通测试 —— 完全二叉树、非完全二叉树
- 特殊测试 —— 只要左子节点的二叉树、只有右子节点的二叉树、只有一个结点
- 输入测试 —— 空节点
推荐↓↓↓
长
按
关
注
?【16个技术公众号】都在这里！
涵盖：程序员大咖、源码共读、程序员共读、数据结构与算法、黑客技术和网络安全、大数据科技、编程前端、Java、Python、Web编程开发、Android、iOS开发、Linux、数据库研发、幽默程序员等。
万水千山总是情，点个 “
在看” 行不行
