0998. Maximum Binary Tree II

题目信息

题号:

0998

难度:

Medium

主题:

最大二叉树、数组追加、树结构更新

原题:

LeetCode 0998

重点:

输入树由某个互不相同数组 a 构造但不直接给出 a;把 val 追加到 a 末尾后,返回新数组对应的最大二叉树

题目重述

最大二叉树的构造规则为:数组中的最大值成为根节点,最大值左侧子数组递归构造左子树,右侧子数组递归构造右子树。

给定一棵最大二叉树 root = Construct(a) 和整数 val。原数组 a 未直接提供。令 b 为在 a 末尾追加 val 后得到的数组,并保证 b 中所有值互不相同。请返回 Construct(b) 的根节点。

原树节点数在 [1, 100] 范围内,节点值和 val 均在 [1, 100] 范围内,所有值互不相同。

自建示例

追加的新值大于原树所有节点:

输入:root = [4,null,3,1], val = 5
输出:[5,4,null,null,3,1]
解释:原树对应数组 [4,1,3]。追加 5 得到 [4,1,3,5],最大值 5 成为新根,原整棵树成为其左子树。

追加值小于根节点:

输入:root = [5,3], val = 4
输出:[5,3,4]
解释:原树对应数组 [3,5]。追加 4 得到 [3,5,4],根节点 5 保持不变,新值 4 成为其右孩子。