对于给定的节点：

  • 如果它可以是一个父节点，根据中序遍历的规则，需要输出它右子树中的最左子节点，即代码中的11-15行
  • 如果它不是父节点：（16-19）
    1. 若它是它父节点的左叶子，则返回它的父节点
    2. 若它是右叶子，则不断向上搜索父节点，直至有一个父节点k不是k的父节点的右叶子，此时返回k的父节点。
  • 如果直到根节点上述情况还不成立，有可能该节点是最后一个节点或是输入的二叉树为None，则输出None 
# -*- 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.right:
            pNode = pNode.right
            while pNode.left:
                pNode = pNode.left
            return pNode
        while pNode.next and pNode.next.right == pNode:
                pNode = pNode.next
        if pNode.next:
            return pNode.next
        return None