2. 二叉树的下一个节点

二叉树的下一个结点_牛客题霸_牛客网

题目描述：给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。

示例1:

输入:{8,6,10,5,7,9,11}, 8
返回:9

1. 如果一个节点有右子树，那么它的下一个节点就是它的右子树的最左节点
2. 如果一个节点没有右子树 如果该节点是父节点的左孩子节点，那么下一个节点就是该节点的父节点如果该节点是父节点的右孩子节点，那么就一直向上找它的父节点，直到找到一个节点，是父节点的左孩子节点，此时下一个该节点的下一个节点就是该节点的父节点。如果找到根节点了，就证明到最后了，没有下一个节点了。

class Solution 
{
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode) 
    {
        // 1.一个节点有右子树
        if(pNode->right != nullptr) {
            pNode = pNode->right;
            while(pNode->left != nullptr)
                pNode = pNode->left;
            return pNode;
        }
        auto parent = pNode->next;
        // 2.1没有右子树, 该节点是父节点的左孩子节点
        if(parent != nullptr && parent->left == pNode)
            return parent;
        // 2.2没有右子树, 该节点是父节点的右孩子节点
        while(parent != nullptr) {
            pNode = parent;
            parent = pNode->next;
            if(parent == nullptr)    break;
            if(pNode == parent->left)
                return parent;
        }
        return nullptr;
    }
};