每日一练（剑指offer）二叉树的下一个结点

输入描述：

输入分为2段，第一段是整体的二叉树，第二段是给定二叉树节点的值，后台会将这2个参数组装为一个二叉树局部的子树传入到函数GetNext里面，用户得到的输入只有一个子树根节点

返回值描述：

返回传入的子树根节点的下一个节点，后台会打印输出这个节点

示例

输入：

{8,6,10,5,7,9,11},8

复制

返回值：

9

思路

1pNode有无右子树，有→2，无→3；

2有右子树，找到右子树的最左节点返回即可；

3无右子树，则中序输出的下一节点必然在pNode的上层。看→4；

4上层为左节点，返回即可；上层为右节点，找上层的上层，重复4。

/**
 * struct TreeLinkNode {
 *   int val;
 *   struct TreeLinkNode *left;
 *   struct TreeLinkNode *right;
 *   struct TreeLinkNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pNode TreeNode类 
 * @return TreeNode类
 */
struct TreeLinkNode* GetNext(struct TreeLinkNode* pNode ) {
    // write code here
    struct TreeLinkNode*tmp;
    if(!pNode)return pNode;
    if(pNode->right==NULL){//如果pNode没有右子树
    //判断pNode是pNode父节点的左孩子还是右孩子
    while(pNode->next)
    {
        tmp=pNode->next;
        if(pNode==tmp->left)return pNode->next;
        pNode=pNode->next;
    }
    return NULL;
    }else{
        //如果pNode有右子树
        tmp=pNode->right;
        while(tmp->left)
        {
            tmp=tmp->left;
        }
    }
    return tmp;
}