《剑指offer》面试题8:二叉树的下一个节点

马谦马谦马谦 数据结构和算法评论493字数 617阅读2分3秒阅读模式

一、题目

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

以下面的二叉树为例,它的中序遍历序列是:[2, 4, 1, 5, 3, 6],节点4的下一个节点是1,节点3的下一个节点是5。

《剑指offer》面试题8:二叉树的下一个节点-图片1

二、分析

画出上面这棵二叉树的中序遍历过程为:

《剑指offer》面试题8:二叉树的下一个节点-图片2

根据中序遍历的特性,可以整理出来的下一个节点的规律:

  1. 如果节点有右子节点,那么下一个节点一定在右子树中,这种又分成了2种情况。
    • 右儿子没有子节点,那么下一个节点就是子节点(节点2
    • 如果右子节点有子节点,下一个节点就是右子节点种最左的节点(节点1)。
  2. 如果节点没有右子节点,并且是父节点的左子节点,那么下一个节点就是父亲节点(节点5)。
  3. 如果节点没有右子节点,并且是父节点的右子节点,那就递归查找父节点,直到一个父节点是祖父节点的左子树(节点4)。如果找到根节点都没有找到,就说明该节点已经是最后一个了(节点6)。

三、代码

类节点定义:

查找中序遍历序列中下一个节点的成员函数:

四、单元测试

单元测试主要覆盖几个点:

  • 节点有右子节点。
  • 节点没有右子节点,存在一个父节点是祖先节点的左子节点。
  • 节点没有右子节点,不存在一个父节点是祖先节点的左子节点。

测试结果:

《剑指offer》面试题8:二叉树的下一个节点-图片3

 
马谦马谦马谦
  • 本文由 马谦马谦马谦 发表于 2020年2月8日15:41:21
  • 转载请务必保留本文链接:https://www.dyxmq.cn/program/algorithms/next-node-in-binary-trees.html
匿名

发表评论

匿名网友
:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:
确定

拖动滑块以完成验证