题目描述:给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。
问题分析:根据中序遍历的特点,当前节点的下一节点有三种可能,举例如下图:
(1)当前节点有右孩子,那么下一节点就是该右孩子的最左叶节点。如上图B节点
(2)当前节点没有右孩子,并且当前节点是其父节点的右孩子,那么下一节点是其父节点的父节点。如上图D节点
(3)当前节点没有右孩子,并且当前节点是其父节点的左孩子,那么下一节点是其父节点。如上图E节点
代码截图: