二叉树的下一个结点

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

# -*- coding:utf-8 -*-
class TreeLinkNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        self.next = None

# just follow the traversal pipeline is ok
class Solution:
    def GetNext(self, p):
        while True:
            if p.right:
                t = p.right
                while t.left: t=t.left
                return t
            r = p.next
            while r and r.right==p:
                p = r
                r = r.next
            if not r: return None
            if r.left==p: return r
            p = r
        return None