解法一：分三种情况讨论 题解 | #二叉树的下一个结点#

/*
struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next;
    TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
        
    }
};
*/
#include <cstddef>
#include <cstdio>
class Solution {
public:
    TreeLinkNode* cur;
    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
        if(pNode == NULL){
            return nullptr;
        }
        if(pNode->right)
        {
            // 如果当前结点有右子节点，则下一个结点即为该右子节点最左下的结点     
            while(pNode->right->left!=nullptr){
                pNode->right = pNode->right->left;
            }
            return pNode->right;
        }
        else{
            // 如果当前结点没有右子节点，且当前节点是其父亲节点的左子节点，则返回其父亲节点。
            if(pNode->next && pNode->next->left == pNode){
                return pNode->next;
            }
            // 如果当前结点没有右子节点，且当前结点是其父亲节点的右子节点，则需要沿着左上方父亲节点爬树，直到爬到当前结点是其父亲节点的左子节点为止，返回当前结点的父结点即可。
            if(pNode->next && pNode->next->right == pNode){
                while(pNode->next && pNode==pNode->next->right)
                {
                    pNode = pNode->next;
                }
                return pNode->next;
            }
            return nullptr;
		} 
    }
};

1 如果当前结点有右子节点，则返回其右子树的最左小节点。

2.如果当前结点没有右子节点，且当前结点是其父结点的左子节点，则返回其父结点。

3.如果当前结点没有右子节点，且当前结点是其父结点的右子节点，则沿着其父结点往左上方爬，直到当前结点为其父结点的左子节点，返回其父结点即可。否则返回NULL.