题目描述

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
说明：本题目包含复杂数据结构TreeLinkNode，点此查看相关信息

  1. # -*- coding:utf-8 -*-
  2. # class TreeLinkNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.left = None
  6. #         self.right = None
  7. #         self.next = None
  8. class Solution:
  9.     def GetNext(self, pNode):
  10.         # write code here
  11.         if not pNode:
  12.             return None
  13.         if pNode.right:
  14.             pNode = pNode.right
  15.             while pNode.left:
  16.                 pNode = pNode.left
  17.             return pNode
  18.         while pNode.next:
  19.             if pNode.next.left==pNode:
  20.                 return pNode.next
  21.             else:
  22.                 pNode = pNode.next
  23.         return None