剑指offer：二叉树的下一个节点

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

class TreeLinkNode: def __init__(self, x): self.val = x self.left = None self.right = None self.parent = None class Solution: """ 给定节点，求中序遍历下该节点的下一个节点 """ def GetNext(self, pNode): if not pNode: return None # 如果给定节点存在右子树，则下一个节点就是右子树的最左叶子节点 if pNode.right: temp = pNode.right while temp.left: temp = temp.left return temp if pNode.parent: # 如果给定节点不存在右子树，则找到第一个在它右边的祖先节点 # 例如，给定节点是父节点的左子节点，则下一个节点就是父节点 current = pNode parent = pNode.parent # 如果给定节点是父节点的右子节点，则需要继续往上找，找到第一个祖先节点， # 使得该祖先节点的是其父节点的左子节点，则下一个节点就是该祖先节点的父节点(因为给定 # 节点是该祖先节点的父节点左边最近的子节点) while parent and current == parent.right: current = parent parent = parent.parent return parent # 给定节点已是最右节点，不存在下一个节点 return None