二叉树的下一个节点——jzoffer

题目：给定一个二叉树和其中一个节点，如何找出中序遍历序列的下一个节点？树中的节点除了有两个分别指向左、右节点的指针，还有一个指向父节点的指针。

• 如果该节点有右子树，那么next就是右子树的最左叶节点
• 如果该节点没有右子树
  • 该节点是其父节点的左子节点，那么next就是该节点的父节点
  • 该节点是其父节点的右子节点，往父节点方向迭代，如果遇到一个节点a，a是其父节点b的右子节点，继续迭代，直到a是其父节点b的左子节点为止，那么next就是b节点
  • 如果第二种情况不存在，那么代表没有next

'''
class TreeNode:
    def __init__(self, val)
        self.val = val
        self.left = None
        self.right = None
        self.parent = None
'''
class Solution:
    def get_next(self, node):
        if not node:
            return False
        next_node = None
        if node.right:
            ret = node.right
            while ret.left:
                ret = ret.left
            next_node = ret
        elif node.parent:
            '''
             _parent = node.parent
            if _parent.left and _parent.left == node:
                next_node = _parent
            else:
                while _parent.parent：
                    _parent = _parent.parent           
            '''
            p_current = node
            p_parent = node.parent
            while p_parent and p_current == p_parent.right:
                p_current = p_parent
                p_parent = p_parent.parent
            next_node = p_parent
        return next_node