py3

# -*- coding:utf-8 -*-
# class TreeLinkNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.next = None
class Solution:
    def GetNext(self, pNode):
        # write code here
        # 情况一，有右子树,找到右子树的叶子左节点
        if pNode.right:
            pNode = pNode.right
            while pNode.left:
                pNode = pNode.left
            return pNode
        # 情况二，没有右子树，且不为根节点，且为父节点的左子树,返回父节点
        if pNode.next and pNode == pNode.next.left:
            return pNode.next
        # 情况三，没有右子树，且不为根节点，找到第一个为父节点左子树的节点，返回其父节点
        if pNode.next:
            while pNode.next and pNode == pNode.next.right:
                pNode = pNode.next
            return pNode.next
        # 根节点，没有右子树，直接返回空
        return None