0998. Maximum Binary Tree II¶
题目信息¶
- 题号:
0998
- 难度:
Medium
- 主题:
最大二叉树、数组追加、树结构更新
- 原题:
- 重点:
输入树由某个互不相同数组
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 成为其右孩子。