题解 | #二叉树的下一个结点#

解题思路：分两种情况来处理，1.如果该节点有右子树，则中序遍历的下一个节点是该节点右子树的左到不能左的节点；2.如果该节点没有右子树，则看该节点的父节点；如果该节点是它父节点的左子节点，那么中序遍历的下一个节点就是该节点的父节点；3.如果该节点既没有右子树，并且它还是它父节点的右子节点，那么这个情况就比较复杂，需要沿着指向父节点的指针一直向上遍历，直到找到一个是它父节点的左子节点的节点。如果这样的节点存在，那么这个节点的父节点就是我们要找的中序遍历的下一个节点。

时间复杂度：O(n)

空间复杂度：O(1)

基于C++实现的：

class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
        //判断节点为空的情况
        if(pNode == nullptr){
            return nullptr;
        }
        TreeLinkNode *pNodenext = nullptr;
        //如果pNode有右子树，则中序遍历的下一个节点是右子树的最左节点；
        if(pNode->right != nullptr){
            pNodenext = pNode->right;
            if(pNodenext->left != nullptr){
                pNodenext = pNodenext->left;
            }
            return pNodenext;
        }
        //如果pNode没有右子树，则判断pNode的父节点
        while(pNode->next){
            pNodenext = pNode->next;
            if(pNode == pNodenext->left){
                return pNodenext;
            }
            pNode = pNode->next;
        }
        return nullptr;
    }
};

基于python实现：

class Solution:
    def GetNext(self, pNode):
        # 空节点情况
        if not pNode:
            return pNode
        # 有右子树的情况
        while pNode.right:
            p = pNode.right
            if p.left:
                p = p.left
            return p
        # 无右子树，考虑父节点的情况
        while pNode.next:
            p = pNode.next
            if p.left == pNode:
                return p
            pNode=p