题目:

给定一个搜索二叉树的头节点a,和这个二叉树中的任一节点b,用一个函数实现返回在这棵树中,节点b的后继节点。

jj001

2的后继节点为3,4的后继节点为5,5的后继节点为6。

难度:校

解法:

看着容易,实现完全不出错比较难。首先有一个边界条件我们要考虑到,在一棵搜索二叉树中总有一个节点是没有后继节点的,就是最大的那个节点(本例的9节点)。

仔细分析后,找节点S的后继节点有如下几种情况:

情况一:如果S为头

1)如果S有右子树,那么S的后继节点为S右子树最左边的节点。例如例子里的5。

2)如果S没有右子树,那么S是整个树中最大的节点,S没有后继节点。

情况二:如果S不是头

1)如果S有右子树,那么S的后继节点为S右子树最左边的节点。如例子里的0,2,3,8,

2)如果S没有右子树,那么S的后继节点为S的某一个祖先节点,这个祖先节点满足甲乙两个条件:
甲,S是这个祖先节点左子树的成员;
乙,在满足条件甲的所有S祖先节点中,离S最近的祖先节点就是S的后继节点。
例子中节点1就是这种情况,节点1不是头,也没有右子树。
节点0是节点1的祖先节点,但是不满足条件甲;节点1的另外两个祖先节点(2和5)都满足条件甲,但是节点2是离节点1最近的。所以节点1的后继节点是2。

3)如果1)和2)都找不到后继节点,说明S没有后继节点,例子里的9节点。

代码:

本文章原始出处”脑客爱刷题”  www.knockgate.com 版权所有,转载请标明出处!

1 条评论

欢迎留言