二叉树下一个节点详解让人头大两小时剑指offer（数据结构基础回顾）

题目如下所示：

给定一个二叉树及其中的一个节点，请确定其在中序遍历序列中的后续节点并予以返回。请注意以下几点：第一，在该二叉树中每个节点不仅拥有左右子节点属性还带有指向其父节点的指针字段；第二，在实现过程中需要注意区分根节点与普通节点的行为差异；第三，在算法设计时应充分考虑时间和空间复杂度优化的需求。

给定一个二叉树及其中的一个节点，请确定其在中序遍历序列中的后续节点并予以返回。请注意以下几点：第一，在该二叉树中每个节点不仅拥有左右子节点属性还带有指向其父节点的指针字段；第二，在实现过程中需要注意区分根节点与普通节点的行为差异；第三，在算法设计时应充分考虑时间和空间复杂度优化的需求。

它的数据结构如下所示**：**

我们定义了一个名为TreeLinkNode的结构体。
该结构体包含了整数值val。
其左子节点指针域为left。
其右子节点指针域为right。
其下一个节点指针域为*next。
构造函数接受一个整数x进行初始化，并设置各指针域值为NULL。

}
};
/*

看起来其实很简单嘛？不就是利用中序遍历找到给定节点之后的那个邻接节点吗？毕竟题目已经明确给出了各节点之间的父子关系呢。按照中序遍历的基本原则进行处理就足够了。却意外地遇到了一些问题，在解决这道题的过程中整个思考过程非常细致周密而没有遗漏任何关键点但最终还是会出现下图所示的情况：

![]