面试题8：找出中序遍历的下一个节点

给定一颗二叉树和其中的一个节点，找出中序遍历序列中的下一个节点。树节点的结构声明为

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

解析：分两种情况：

• 如果这个节点有右子树：下一个遍历的节点就是右子树中最靠左的节点；
• 如果这个节点没有右子树：
  -- 如果这个节点是根节点，那就没有下一个遍历的节点；
  -- 如果这个节点是左节点，那么下一个遍历的节点是这个节点的双亲节点；
  -- 如果这个节点是有节点，那么下一个遍历的节点就需要向上找，找到第一个是左节点的双亲节点，并返回这个双亲节点的双亲节点；如果找不到的话就说明没有下一个要遍历的节点。

答案：

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;
}