面试题8：二叉树的下一个节点

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

解题思路：
首先需要弄清楚这个节点的情况，然后分别进行应对。
① 如果该节点有右子树，下一节点为其右子树的最左节点；
②如果该节点没有右子树，且为父节点的左子树，那么下一节点为其父节点；
③如果该节点没有右子树，且为父节点的右子树，则需要一直向上遍历，直到某一节点为其父节点的左子树，下一节点则为其父节点，否则没有下一节点。

代码:

class Solution:
    def GetNext(self, pNode):
        # write code here
        if not pNode:
            return
        elif pNode.right != None:    #如果该节点有有右子树，下一节点为右子树的最左节点
            pNode = pNode.right
            while pNode.left != None:
                pNode = pNode.left
            return pNode

        elif pNode.next != None and pNode.next.left == pNode: #如果该节点没有右子树并且是其父节点的左节点，返回其父节点
            return pNode.next

        else:
            #如果该节点没有右子树并且是其父节点的右节点，一直向上遍历直到找到一个节点是其父节点的左节点
            while pNode.next != None and pNode.next.left != pNode: 
                pNode = pNode.next
            return pNode.next