在二叉树中找到一个节点的后继节点

题目描述:

该结构比普通二叉树节点结构多了一个指向父节点的parent指针。假设有一 棵Node类型的节点组成的二叉树,树中每个节点的parent指针都正确地指向 自己的父节点,头节点的parent指向null。只给一个在二叉树中的某个节点 node,请实现返回node的后继节点的函数。在二叉树的中序遍历的序列中, node的下一个节点叫作node的后继节点。

解题思路:

首先要明确是中序遍历;
通过观察中序遍历的规律,可以发现:
1、如果一个节点有右孩子,右孩子同样也是左中右的顺序,那么这个节点的后继节点就是右孩子中最左的节点;
2、如果一个节点没有右孩子:
2.1:如果这个节点是上一节点的左孩子,那这个节点的后继节点就是上一节点;
2.2:如果这个节点是上一节点的右孩子,那就向上查找,直到该节点是上一节点的左孩子,返回父节点;
在二叉树中找到一个节点的后继节点
在二叉树中找到一个节点的后继节点