题解 | #二叉树的下一个结点#

• 分类讨论解法

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

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

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

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

/**
 * 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* 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;
}

• 遍历暴力解法

/**
 * struct TreeLinkNode {
 *	int val;
 *	struct TreeLinkNode *left;
 *	struct TreeLinkNode *right;
 *	struct TreeLinkNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pNode TreeNode类 
 * @return TreeNode类
 */
struct Node{
    struct TreeLinkNode* tree;
    struct Node* next;
};

struct sNode{
    struct Node* rear;
};

struct sNode *createStack(){
    struct sNode* tmp;
    tmp = (struct sNode*)malloc(sizeof(struct sNode));
    tmp->rear = NULL;
    return tmp;
}

bool isEmpty(struct sNode* tmp){
    if(tmp->rear == NULL)return true;
    else return false;
}

void sPush(struct sNode* tmp, struct TreeLinkNode* tree){
    if(!tmp)tmp=createStack();
    struct Node* tmpNode;
    tmpNode = (struct Node*)malloc(sizeof(struct Node));
    tmpNode->tree = tree;
    tmpNode->next = tmp->rear;
    tmp->rear = tmpNode;
}

struct TreeLinkNode* sPop(struct sNode* tmp){
    if(isEmpty(tmp))return NULL;
    else{
        struct Node* tmpNode;
        tmpNode = (struct Node*)malloc(sizeof(struct Node));
        struct TreeLinkNode* tmpTree;
        tmpTree = (struct TreeLinkNode*)malloc(sizeof(struct TreeLinkNode));
        tmpNode = tmp->rear;
        tmpTree = tmpNode->tree;
        tmp->rear = tmpNode->next;
        free(tmpNode);
        return tmpTree;
    }
}
//-----------------------------------------------------//
struct TreeLinkNode* GetNext(struct TreeLinkNode* pNode ) {
    // write code here
    struct sNode* stack;
    stack = createStack();
    struct TreeLinkNode* tmp = pNode;
    struct TreeLinkNode* root;
    //找到根节点，最坏O(n)
    while (tmp) {
        root = tmp;
        tmp = tmp->next;
    }  
    //中序输出，最坏2*O(n):出入栈O(n)，判断是否相等O(n)
    int flag = 0;
    while(root || !isEmpty(stack)){
        while(root){
            sPush(stack, root);
            root = root->left;
        }
        if(!isEmpty(stack)){
            root = sPop(stack);
            if(flag){
                return root;
            }
            if(root->val == pNode->val){
                flag = 1;
            }            
            root = root->right;
        }
    }
    return NULL;
}
//-----------------------------------------------------//