面试题 8：二叉树的下一个节点

08_NextNodeInBinaryTrees.cpp

BinaryTreeNode *GetNext(BinaryTreeNode *pNode) {
    if(pNode == nullptr) {
        return nullptr;
    }
    // 初始化下一个节点
    BinaryTreeNode *pNext = nullptr;
    if(pNode->m_pRight != nullptr) {
        BinaryTreeNode *pRight = pNode->m_pRight;
        while(pRight->m_pLeft != nullptr) {
            pRight = pRight->m_pLeft;
        }
        pNext = pRight;
    }
    else if(pNode->m_pParent != nullptr) {
        BinaryTreeNode *pCurrent = pNode;
        BinaryTreeNode *pParent = pNode->m_pParent;
        while(pParent != nullptr && pCurrent == pParent->m_pRight) {
            pCurrent = pParent;
            pParent = pParent->m_pParent;
        }
        pNext = pParent;
    }
    return pNext;
}