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

class Solution:
    vals = []
    def GetNext(self, pNode):
        # write code here
        if not pNode:
            return None

        root = pNode
        # 找到根节点
        while root.next:
            root = root.next

        self.MidOrder(root)
        
        valCount = len(self.vals)
        valId = self.vals.index(pNode)
        if valId >= 0 and valId + 1 < valCount:
            return self.vals[valId + 1]
        return None

    def MidOrder(self, root):
        if not root:
            return None
    
        self.MidOrder(root.left)
        self.vals.append(root)
        self.MidOrder(root.right)