题目：二叉树的下一个节点

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

解析

通过举例画出二叉树，分情况讨论（有序判断，不可颠倒）：

给定节点含右子节点，判断给定节点右子节点
- 给定节点右子节点含左子节点，取给定节点右子节点左子叶
- 给定节点右子节点含右子节点，取给定节点右子节点
- 给定节点右子节点不含子节点，取给定节点右子节点
给定节点不含右子节点，判断给定节点父节点
- 给定节点为其父节点左子节点，取给定节点父节点
- 给定节点为其父节点右子节点，判断给定节点父节点父节点
  - 给定节点父节点为其父节点左子节点，取给定节点父节点父节点
  - 给定节点父节点为其父节点右子节点，判断给定节点父节点父节点父节点
    - ……（循环往复，直至节点为其父节左子节点）

根据讨论写出如下代码

BinaryTreeNode* findNext(BinaryTreeNode *pNode)
{
    if (nullptr == pNode)
        return nullptr;
    BinaryTreeNode *pNext = nullptr;
    if (pNode->right != nullptr)
    {
        pNext = pNode->right;
        if (pNext->left != nullptr)
        {
            while (pNext->left != nullptr)
                pNext = pNext->left;
            return pNext;
        }
        else
            return pNext;
    }
    else
    {
        pNext = pNode->root;
        while (pNext != nullptr && pNext->right == pNode)
        {
            pNode = pNext;
            pNext = pNode->root;
        }
        return pNext;
    }
}

与书中代码如出一辙😎！

本文采用 CC BY-NC-SA 3.0 Unported 协议进行许可