题目隐含的第一个参数是二叉树(不用管),第二个参数pNode指向二叉树中的一个结点,题目要返回pNode结点在这个二叉树的中序遍历下一个结点地址。

因为中序遍历是左->根->右(简单点就是把树看成整体,不管结点父子关系,按结点从左到右出现的顺序遍历),所以分两种情况讨论:
一:当pNode有右结点时,找到其右结点,并找该右结点的最深左孩子结点(先右一次再左到底),返回最深左结点。
二:当pNode没有右结点时,它的下一个结点为它右边的结点,这个结点如果有只会出现在它的父结点中,只要pNode不在它的父结点的右孩子中,就输出该父结点。
/**
 * struct TreeLinkNode {
 *	int val;
 *	struct TreeLinkNode *left;
 *	struct TreeLinkNode *right;
 *	struct TreeLinkNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static,防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param pNode TreeNode类 
 * @return TreeNode类
 */
struct TreeLinkNode* GetNext(struct TreeLinkNode* pNode ) {
    // write code here
    struct TreeLinkNode *p=pNode,*q;
    if(p->right!=0){//为非叶结点且有右孩子
        p=p->right;
        while(p->left){
            p=p->left;
        }
        return p;
    }
    else{//为叶结点或者只有左孩子
        while(p->next){
            q=p;
            p=p->next;
            if(p->right!=q){
                return p;
            }
        }
        return NULL;
    }
}