二叉树的下一个节点（再重做）

image.png

分三步进行思考：

1. 当前节点有右子树，那么下一个节点是右子树里面的最左边的那个
   2.如果当前节点没有右子树，但是当前节点是父节点的左节点，那么下一个节点就是父节点
   3.如果当前节点没有右子树，且是父节点的右节点，则一直向上追溯，直到某个祖先是其父节点的左孩子，那个返回这个祖先的父节点。如果一直到根都没有，则返回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 is None:
            return None
        if pNode.right:
            p = pNode.right
            while p.left:
                p = p.left
            return p
        else:
            if not pNode.next:
                return None
            if pNode.next.left == pNode:
                return pNode.next
            else:
                p = pNode
                while p.next:
                    if p.next.left == p:
                        return p.next
                    p = p.next
                return None