二叉树的下一个结点

题目描述

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

• 数据结构：

 class TreeLinkNode:
     def __init__(self, x):
         self.val = x
         self.left = None
         self.right = None
         self.next = None next是指向父节点的

• 解题思路：
  举例子总结可能遇到的情况：1）给定节点为某根节点，因为是中序遍历，因此只要关心右子树，只要右子树不为空，那就从右子树中找出最左下的节点，即第一个左孩子为空的节点；2）给定的节点为叶子节点，观察中序遍历规律可知，要找的是向上遍历第一个有左子树的节点；3）没有右子树的根节点，可以发现和第二种是同样的找法，还是要找到第一个有左子树的祖宗节点。

• 解题代码：

class Solution:

    def GetNext(self, pNode):
        # write code here
        temp=pNode
        if temp.right:
            temp=temp.right
            while temp.left:
                temp=temp.left
            return temp
        else:
            last=temp.next
            while last is not None and last.left!=temp:
                temp=temp.next
                last=temp.next
            return last