# -*- 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:  # 该节点有右子树

            p = pNode.right #将右子树第一个节点作为P

            while p.left:

                p = p.left #然后找其左子树最左边

            return p

        while pNode.next:  # 无右子树，则找第一个当前节点是父节点左孩子的节点

            if (pNode.next.left == pNode): #如果pNode节点的父节点的左节点是pNode

                return pNode.next #则该节点的父节点为中序遍历下一个节点

            pNode = pNode.next  # 沿着父节点向上遍历

        return  # 到了根节点仍没找到，则返回空