计算二叉树的下一个节点

分三种情况分别讨论，注意不能访问空指针（非法访问）

/*
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(pNode==nullptr) return nullptr;
        // 第一种情况，如果一个节点有右子树，那么中序遍历中下一个元素为其右子树的最左边的节点
        if(pNode->right!=nullptr)
        {
            auto tmp_ptr = pNode->right;
            while(tmp_ptr->left){
                tmp_ptr = tmp_ptr->left;
            }
            return tmp_ptr;
        }

        if(pNode->next == nullptr)
        {
            return nullptr;
        }
        // 第二种情况，该节点无右子树，且是父节点的左节点，那么next为其父节点
        else if(pNode->next->left == pNode){
            return pNode->next;

        }

        // 第三种情况，该节点无右子树，且是父节点的右节点，
        // 那么一直网上查，查到一个左子节点a,则a的父节点就是所求
        else{
            auto tmp_ptr = pNode->next;
            if(tmp_ptr==nullptr) return nullptr;
            if(tmp_ptr->next==nullptr) return nullptr;
            while(tmp_ptr->next->left != tmp_ptr)
            {
                tmp_ptr = tmp_ptr->next;
                if(tmp_ptr==nullptr || tmp_ptr->next==nullptr)
                {
                    return nullptr;
                }
            }
            return tmp_ptr->next;

        }
    }
};