题目描述：

给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。下图为一棵有9个节点的二叉树。树中从父节点指向子节点的指针用实线表示，从子节点指向父节点的用虚线表示.

示例:
输入:{8,6,10,5,7,9,11},8
返回:9
解析:这个组装传入的子树根节点，其实就是整颗树，中序遍历{5,6,7,8,9,10,11}，根节点8的下一个节点就是9，应该返回{9,10,11}，后台只打印子树的下一个节点，所以只会打印9，如下图，其实都有指向左右孩子的指针，还有指向父节点的指针，下图没有画出来

题解1：使用数组，将二叉树的中序遍历结果存放在数组中，直接寻找到某结点的下一个结点。

步骤：

1. 寻找到二叉树的根节点。由于提供了指向父亲结点的指针，因此，当next == NULL时，为二叉树根节点。
2. 中序遍历二叉树，并将结果存放在数组中。
3. 找到当前结点，返回当前结点的下一个结点。

代码：

/*
struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next;
    TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
        
    }
};
*/
//中序遍历
void preOrder(TreeLinkNode * t,vector<TreeLinkNode *> &v){
    if(NULL == t) return;
    preOrder(t->left, v);//访问左子树
    v.push_back(t);//将根结点放入vector容器中
    preOrder(t->right, v);//访问右子树
}
class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
        if(NULL == pNode) return NULL;
        TreeLinkNode * temp = pNode;
        //寻找根节点
        while(temp->next != NULL){
            temp = temp->next;
        }
        //中序遍历二叉树，并将遍历结果存放在vector中
        vector<TreeLinkNode*> v;
        preOrder(temp, v);//从根节点开始遍历
        //直接在vector容器中找到该节点的下一个结点
        for(int i = 0 ; i < v.size(); i++){
            if(v[i] == pNode && i < v.size()){
                return v[++i];//结点i的下一个结点
            }
        }
        return NULL;
    }
};

题解2：最优解-引自牛客提霸

红色数字是中序遍历的顺序。接下来，我们就假设，如果当前结点分别是1,2 ... 7，下一结点看有什么规律没？

1 => 2 // 显然下一结点是 1 的父亲结点
2 => 3 // 下一节点是当前结点右孩子的左孩子结点，其实你也应该想到了，应该是一直到左孩子为空的那个结点
3 => 4 // 跟 2 的情况相似，当前结点右孩子结点的左孩子为空的那个结点
4 => 5 // 5 是父亲结点 3 的父亲结点，发现和1有点像，因为 1，3,同样是父亲结点的左孩子
5 => 6 // 跟 4=>5 一样的道理
6 => 7 // 跟 3=>4 一样的道理
7 => null // 因为属于最尾结点

总结： 此时，可以总结一下：
[1] 是一类：特点：当前结点是父亲结点的左孩子
[2 3 6] 是一类，特点：当前结点右孩子结点，那么下一节点就是：右孩子结点的最左孩子结点,如果右孩子结点没有左孩子就是自己
[4 5]是一类，特点：当前结点为父亲结点的右孩子结点，本质还是[1]那一类
[7]是一类，特点：最尾结点

/*
struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next;
    TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
        
    }
};
*/

class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
        if(NULL == pNode) return NULL;
        
        //若有右子树，寻找右子树的最左边孩子
        TreeLinkNode *temp =pNode->right;
       if(temp){
           while(temp->left != NULL)//始终指向左孩子
               temp = temp->left;
           return temp;
       }
        
        //若没有右子树，找最右父结点
        temp = pNode;
        while(temp->next){
            if(temp->next->left == temp){
                return temp->next;//找到了，返回下一个结点
            }
            temp = temp->next;
        }
        return NULL;
    }
};