题解 | #二叉树的下一个结点#

# -*- coding:utf-8 -*-
# class TreeLinkNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.next = None
class Solution:
    def __init__(self):
        self.nodes = []

    def GetNext(self, pNode):
        # write code here
        # print(pNode)
        # print()
		'''
		找到树的根然后利用树的根找到中序遍历树的所有节点，按中序遍历的顺序添加到nodes列表中
		'''
        root = pNode
        while root.next:
            root = root.next

        self.MiddleTravel(root)

        for i in range(len(self.nodes)-1):
            if self.nodes[i] == pNode:
                return self.nodes[i+1]
	   #如果没有在nodes列表中找到和pNode相同的节点，返回None
        return None

    def MiddleTravel(self, root):
        if not root:
            return 
        self.MiddleTravel(root.left)
        self.nodes.append(root)
        self.MiddleTravel(root.right)