题解 | #二叉树的下一个结点#都是细节呐

/*
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 && pNode->next == nullptr) return nullptr;

        if (pNode->right == nullptr) {
            // pNode是左节点时向上回溯
            if (pNode == pNode->next->left) return pNode->next; 
            // pNode是右节点时向上回溯
            TreeLinkNode* father_node = pNode->next;
            do {
                if (father_node->right != pNode) break;
                pNode = father_node;
                father_node = pNode->next;
                if (father_node == nullptr) return nullptr;
            } while(true);
            return father_node;
        }

        TreeLinkNode* ret_node = pNode->right;
        while (ret_node->left != nullptr) ret_node = ret_node->left;
        return ret_node;
    }
};