原题地址
二叉树的下一个节点:https://www.acwing.com/problem/content/description/31/
题目：
给定一棵二叉树的其中一个节点，请找出中序遍历序列的下一个节点。
注意：
1.如果给定的节点是中序遍历序列的最后一个，则返回空节点;
2.二叉树一定不为空，且给定的节点一定不是空节点；
样例
假定二叉树是：[2, 1, 3, null, null, null, null]， 给出的是值等于2的节点。
则应返回值等于3的节点。
解释：该二叉树的结构如下，2的后继节点是3。
2
/ \
1 3
题解
题解思路主要来自y神：https://www.acwing.com/solution/content/714/
我只是记录一下，便于以后复习
这题的思路就是让我们求二叉树中给定节点的后继。
所以我们可以分为两种情况：
1）如果当前节点有右儿子，则右子树中最左侧的节点就是当前节点的后继。比如F的后继是H；
2) 如果当前节点没有右儿子且当前结点是其father结点的右结点，则把他指向它的father结点；当father结点为NULL或者它不在是它父亲结点的右结点时，循环结束，然后再指向它的下一个父节点。例：D的后继结点怎么求：
C的左节点等于D，然后F的左节点不等于C，则循环结束，然后指向C的父节点，则F是D是后继。
代码
class Solution{
public:
TreeNode* inorderSuccessor(TreeNode* p)
{
//第一种情况
if(p->right)
{
p=p->right;
while(p->left)
p=p->left;
return p;
}
//第二种情况
while(p->father&&p==p->father->right)
p=p->father;
return p->father;
}
};