給定一顆二叉樹(shù)和其中的一個(gè)節(jié)點(diǎn)，找出中序遍歷序列中的下一個(gè)節(jié)點(diǎn)。樹(shù)節(jié)點(diǎn)的結(jié)構(gòu)聲明為

struct BTreeNode
{
    int        value;
    BTreeNode* pLeft;
    BTreeNode* pRight;
    BTreeNode* pParent;
};

解析：分兩種情況：

• 如果這個(gè)節(jié)點(diǎn)有右子樹(shù)：下一個(gè)遍歷的節(jié)點(diǎn)就是右子樹(shù)中最靠左的節(jié)點(diǎn)；
• 如果這個(gè)節(jié)點(diǎn)沒(méi)有右子樹(shù)：
  -- 如果這個(gè)節(jié)點(diǎn)是根節(jié)點(diǎn)，那就沒(méi)有下一個(gè)遍歷的節(jié)點(diǎn)酪碘；
  -- 如果這個(gè)節(jié)點(diǎn)是左節(jié)點(diǎn)，那么下一個(gè)遍歷的節(jié)點(diǎn)是這個(gè)節(jié)點(diǎn)的雙親節(jié)點(diǎn)盐茎；
  -- 如果這個(gè)節(jié)點(diǎn)是有節(jié)點(diǎn)兴垦，那么下一個(gè)遍歷的節(jié)點(diǎn)就需要向上找，找到第一個(gè)是左節(jié)點(diǎn)的雙親節(jié)點(diǎn)字柠，并返回這個(gè)雙親節(jié)點(diǎn)的雙親節(jié)點(diǎn)探越；如果找不到的話就說(shuō)明沒(méi)有下一個(gè)要遍歷的節(jié)點(diǎn)。

答案：

inline bool isRoot(BTreeNode *pNode)
{
    if (nullptr == pNode) return false;
    return nullptr==pNode->pParent;
}

inline bool isLeft(BTreeNode *pNode)
{
    if (nullptr == pNode) return false;
    if (nullptr != pNode->pParent)
        return pNode == pNode->pParent->pLeft;
    return false;
}

inline bool isRight(BTreeNode *pNode)
{
    if (nullptr == pNode) return false;
    if (nullptr != pNode->pParent)
        return pNode == pNode->pParent->pRight;
    return false;
}

BTreeNode* GetNext(BTreeNode* pNode)
{
    if (pNode == nullptr) return nullptr;

    //if this node has a right subtree
    if (nullptr != pNode->pRight)
    {
        auto pTemp = pNode->pRight;
        while (nullptr != pTemp->pLeft) pTemp = pTemp->pLeft;
        return pTemp;
    }

    //if this node doesn't have a right subtree
    else
    {
        if (isRoot(pNode)) return nullptr;
        else if (isLeft(pNode))
            return pNode->pParent;
        else if (isRight(pNode))
        {
            while (isRight(pNode)) pNode = pNode->pParent;
            if (isLeft(pNode)) return pNode->pParent;
            else if (isRoot(pNode)) return nullptr;
        }
    }

    return nullptr;
}