二叉树的下一个节点.md

二叉树的下一个节点

知识点：

题目描述

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

解题思路

考虑两种情况：

• 当前节点有右子树，那么其中序遍历的下一个一定是其右子树的最左根
• 当前节点无右子树，则其中序遍历的下一个一定是其祖先节点，同时需要满足本节点是祖先节点的右子节点才可以

代码

class Solution:
    def GetNext(self, pNode):
        # write code here
        if pNode.right is not None:
            rightNode = pNode.right
            while rightNode.left is not None:
                rightNode = rightNode.left
            return rightNode
        else:
            parent = pNode.next
            curNode = pNode
            if parent == None:
                return None
            while parent.right == curNode:
                curNode = parent
                parent = parent.next
                if parent == None:
                    return None

            return parent

这里