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