寻找下一个结点

请设计一个算法，寻找二叉树中指定结点的下一个结点（即中序遍历的后继）。

给定树的根结点指针TreeNode* root和结点的值int p，请返回值为p的结点的后继结点的值。保证结点的值大于等于零小于等于100000且没有重复值，若不存在后继返回-1。

方法一：

中序遍历，利用信号变量，保存下一个节点值

class Successor:
    def findSucc(self, root, p):

        # write code here
        self.status = False
        self.res = -1
        self.checkit(root,p)

        return self.res

    def checkit(self,root,p):
        if not root:
            return
        self.checkit(root.left,p)
        if self.status:
            self.res = root.val
            self.status = False
            return
        if root.val==p:
            self.status = True

        self.checkit(root.right,p)  
        

方法二：

利用辅助数组，把全体节点值存储在数组中

class Successor:
    def findSucc(self, root, p):
        # write code here
        self.arr = []
        self.dfs(root)
        return self.arr[self.arr.index(p) + 1]
 
    def dfs(self, root):
        if not root:
            return
        self.dfs(root.left)
        self.arr.append(root.val)
        self.dfs(root.right)