剑指offer刷题笔记57（python）
题目描述
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
思路
中序遍历序列，可能会出现以下三种情况：
当当前节点有右子树时，下一个节点是它的右子树的最左节点，当当前节点没有右子树，但是有父节点且是他父节点的左子节点时，下一个节点是它的父节点当当前节点既没有右子树同时也是它父节点的右子节点时，要往上寻找，直到某一个节点的父节点的左子节点为该节点，则该节点的下一个节点就是当前节点的下一个节点。
代码
class Solution:
def GetNext(self
, pNode
):
if pNode
== None:
return None
if pNode
.right
:
p
= pNode
.right
while p
.left
:
p
= p
.left
return p
p
= pNode
.next
if p
and p
.left
== pNode
:
return p
else:
while(p
and p
.left
!= pNode
):
pNode
= p
p
= p
.next
return p
