面试题8：二叉树的下一个节点python

题目描述
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
解题思路：
共分为三种情况：

1. 该节点有右孩子，则下一节点为他右子树的中序遍历的第一个值
2. 该节点没有右孩子，则需要去找其父亲节点
   2.1 如果该节点是父亲节点的左孩子，那么下一节点就是该父节点
   2.2 如果该节点是父亲节点的右孩子，那么需要沿着父节点向上遍历，直到找到那个是父节点的左孩子的节点，那么下一节点是该父节点。
   2.3 如果遍历到root根节点仍然没有找到是父节点左孩子的节点，那么则返回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, node):
        # write code here
        # 首先判断该节点有没有右孩子
        if node.right is not None:
            res = self.inorder(node.right)
            return res[0]
        # 在判断他是他父节点的左孩子还是右孩子
        if node.next is not None:
            father = node.next
            # node是父亲的左孩子
            if father.left == node:
                return father
            #node是父亲的右孩子，那么沿着指向父节点的指针一直向上遍历直到找到一个是
            # 它父节点的左孩子的节点。
            else:
                while father.next != None and father.left != node:
                    node = father
                    father = node.next
                if father.left == node:
                    return father
        return None

    #中序遍历
    def inorder(self, root):
        if root is None:
            return []
        res = []
        res += self.inorder(root.left)
        res.append(root)
        res += self.inorder(root.right)
        return res