题目描述：

给定一棵二叉树的其中一个节点，请找出中序遍历序列的下一个节点。

注意：

• 如果给定的节点是中序遍历序列的最后一个，则返回空节点;

• 二叉树一定不为空，且给定的节点一定不是空节点；

数据范围：

树中节点数量 $[0,100]$。

样例：

假定二叉树是：[2, 1, 3, null, null, null, null]， 给出的是值等于2的节点。
则应返回值等于3的节点。
解释：该二叉树的结构如下，2的后继节点是3。
  2
 / \
1   3

样例中的树的中序遍历（左根右）是 $123$，很明显 $2$ 的下一个节点是 $3$
这道题其实是非常经典的树的后继问题，我们可以分三类讨论。
1. $p$ 有右子树，比如下面这副图：

要找结点 $A$ 的后继，其实只要找 $A$ 的右子树中最左边的结点就行了（$G$ 结点），可为什么呢？
因为中序遍历的顺序是左根右，$A$ 点有子树说明不是叶节点，那就不可能是左子树中的结点（因为左子树的点比 $A$ 先被遍历），只能是右子树中的结点。确定了是右子树，那么其实就是找右子树中序遍历中最先被遍历到的结点点，其实就是最左边的结点（因为是左根右）。所以这句话成立。
2. $p$没有右子树，但有父亲，比如下面这幅图：

这种情况下只要找 $E$ 和 $E$ 的祖先中第一个是其父亲的左儿子的结点的父亲就行了，那又为什么呢？
首先，如果 $E$ 是 $E$ 的父亲的左儿子，那么 $E$ 的父亲就是 $E$ 的后继（因为左根右）。
否则，$E$ 是 $E$ 的父亲的右儿子，那么 $E$ 的父亲就不可能是 $E$ 的后继。就在来看以父亲为儿子的树中，如果父亲是左儿子，那就和上面的情况相同；否则根就一定不是后继，后继只可能是 $E$ 的父亲的父亲的父亲。
所以这句话依然成立。
3. 以上两种情况都不满足，则 $p$ 没有后继，返回 $NULL(p->father)$。

代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode *father;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL), father(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* p) {
        //p有右子树
        if (p -> right)
        {
            p = p -> right;
            while (p -> left) p = p -> left;
            return p;
        }
        //p没有右子树
        while (p -> father && p == p -> father -> right)
            p = p -> father;
        //一举两用，如果是第二种情况的话，那么p->father就是答案
        //如果是第三种情况的话p->father也是NULL
        return p -> father;
    }
};

好了，那这篇超详细的题解就到这里了，说的不对的欢迎评论区指正，那我们……

下次再见！！！

$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\mathcal{writer\enspace by \enspace acwing}$ : $\mathfrak{天元之弈}$