动画：面试算法之求二叉树的下一节点
16lz
2021-01-22
题目
给定一棵二叉树和其中的一个的节点，如何找出中序遍历的下一节点。树中的节点除了有两个分别指向左、右子树的指针，还有一个指向父节点的指针。
如：中序遍历序列为 {d,b,h,e,i,a,f,c,g}。
问题分析
我们根据题目进行分析，要想求出其中一个树节点中序遍历的下一节点是什么，我们需要对每个单独的情况分别进行分析。
根据中序遍历的规律（先遍历左子节点，然后遍历根节点，最后遍历右子节点），下一节点可能存在的情况如下。
动画实现
情况一：如果查找的节点有右子树，则下一结点在它右子树的最左子节点。如下图中的 b 节点的下一节点为 h 节点
如果右子树没有左子节点，则下一节点为右子节点。如下图中的 c 节点的下一节点为 g 节点
情况二：如果当前节点没有右子树且是父节点的左子节点，则它的下一节点是它的父节点。如下图中的 d 节点的下一节点为 b 节点。
情况三：如果当前的节点没有右子树且是父节点的右子节点。对于这种情况，我们就一直向它的父节点遍历，直到找到第一个是父节点的左子节点的节点。如果该节点的父节点存在，则父节点就是要查找的下一节点。如下图中的 i 的下一节点为 a。
再比如没有找到这样的节点，下节点为空。如图中的 g 节点的下一结点为空。
代码实现
JavaScript
Java
Python
测试用例
普通测试 —— 完全二叉树、非完全二叉树
特殊测试 —— 只要左子节点的二叉树、只有右子节点的二叉树、只有一个结点
- 输入测试 —— 空节点
更多相关文章
- php+nodeJs+thrift协议，实现zookeeper节点数据自动发现
- jQuery的DOM操作实例（3）——创建节点&&编写一个弹窗
- jQuery编程基础精华02（属性、表单过滤器，元素的each，表单选择器，子元
- 如何在java脚本中获取节点内部文本?
- Study JQuery《zTree自动点击第一个节点》
- 如何使用ajax GET或POST方法将数据传递到amazon lambda节点。js
- jQuery.zTree 点击节点展开折叠子节点
- easyui-tree根据叶子节点获取父节点值(N层)
- PHP递归函数删除所有子节点导致stackoverflow