剑指8：二叉树的下一个节点

传送门

nowcoder

题目描述

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

C++ 代码 - nowcoder

/*
    分析可知：

    1.二叉树为空，则返回空；
    2.如果一个节点有右子树，那么它的下一个节点就是它的右子树的最左子节点。
    3.如果一个节点没有右子树，如果该节点是其父节点的左子节点，那么它的下一个节点就是它的父节点；
      如果一个节点没有右子树，并且该节点是其父节点的右子节点，那么向上遍历直到找到一个是它父节点的左子节点的节点，返回其父节点。
*/
class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
        if (pNode == nullptr) return nullptr;

        // 若当前节点有右子树，则返回右子树的最左子节点
        if (pNode->right != nullptr) {
            pNode = pNode->right;
            while (pNode->left != nullptr) {
                pNode = pNode->left;
            }
            return pNode;
        }

        // 若当前节点没有右子树
        while (pNode->next != nullptr) {
            TreeLinkNode* pRoot = pNode->next;
            if (pRoot->left == pNode) {
                return pRoot;
            }
            pNode = pNode->next;
        }
        return nullptr;
    }
};