题目描述：给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
Solutions
分三个情况讨论每个情况的下一个结点。
# -*- 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 is None:
return
# 如果结点存在右子树，那么下一个结点是右子树最左节点
elif pNode.right is not None:
pNode = pNode.right
while pNode.left is not None:
pNode = pNode.left
return pNode
# 如果一个结点没有右子树，且它还是其父节点的右子树，那么下一个结点就是父节点
elif pNode.next is not None and pNode.next.right is pNode:
while pNode.next is not None and pNode.next.left != pNode:
pNode = pNode.next
return pNode.next
# 如果一个结点是其父节点的左子结点，直接返回其父节点
else:
return pNode.next
# 运行时间：29ms
# 占用内存：6620k