【2022-08-20每日一题】654. 最大二叉树
2022-08-20
4分钟阅读时长
2022-08-20每日一题：654. 最大二叉树
- 难度：Medium
- 标签：栈 、 树 、 数组 、 分治 、 二叉树 、 单调栈
给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
- 创建一个根节点，其值为
nums中的最大值。 - 递归地在最大值 左边 的 子数组前缀上 构建左子树。
- 递归地在最大值 右边 的 子数组后缀上 构建右子树。
返回 nums 构建的 最大二叉树 。
示例 1：
输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]
解释：递归调用如下所示：
- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
- [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
- 空数组，无子节点。
- [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
- 空数组，无子节点。
- 只有一个元素，所以子节点是一个值为 1 的节点。
- [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
- 只有一个元素，所以子节点是一个值为 0 的节点。
- 空数组，无子节点。
示例 2：
输入：nums = [3,2,1] 输出：[3,null,2,null,1]
提示：
1 <= nums.length <= 10000 <= nums[i] <= 1000nums中的所有整数 互不相同
自己写法
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func constructMaximumBinaryTree(nums []int) *TreeNode {
if len(nums) == 0 {
return nil
}
max, idx := nums[0], 0
for i, num := range nums {
if max < num {
idx, max = i, num
}
}
return &TreeNode{max, constructMaximumBinaryTree(nums[:idx]), constructMaximumBinaryTree(nums[idx+1:])}
}
官方
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func constructMaximumBinaryTree(nums []int) *TreeNode {
if len(nums) == 0 {
return nil
}
best := 0
for i, num := range nums {
if num > nums[best] {
best = i
}
}
return &TreeNode{nums[best], constructMaximumBinaryTree(nums[:best]), constructMaximumBinaryTree(nums[best+1:])}
}
复杂度分析
时间复杂度：O(n^2)
空间复杂度：O(n)，即为最坏情况下需要使用的栈空间。
方法二：单调栈
普通版
func constructMaximumBinaryTree(nums []int) *TreeNode {
n := len(nums)
left := make([]int, n)
right := make([]int, n)
for i := range right {
right[i] = -1
}
tree := make([]*TreeNode, n)
stk := []int{-1}
for i, num := range nums {
tree[i] = &TreeNode{Val: num}
for len(stk) > 1 && num > nums[stk[len(stk)-1]] {
right[stk[len(stk)-1]] = i
stk = stk[:len(stk)-1]
}
left[i] = stk[len(stk)-1]
stk = append(stk, i)
}
var root *TreeNode
for i, node := range tree {
l, r := left[i], right[i]
if l == -1 && r == -1 {
root = node
} else if r == -1 || l != -1 && nums[l] < nums[r] {
tree[l].Right = node
} else {
tree[r].Left = node
}
}
return root
}
简写版
func constructMaximumBinaryTree(nums []int) *TreeNode {
tree := make([]*TreeNode, len(nums))
stk := []int{}
for i, num := range nums {
tree[i] = &TreeNode{Val: num}
for len(stk) > 0 && num > nums[stk[len(stk)-1]] {
tree[i].Left = tree[stk[len(stk)-1]]
stk = stk[:len(stk)-1]
}
if len(stk) > 0 {
tree[stk[len(stk)-1]].Right = tree[i]
}
stk = append(stk, i)
}
return tree[stk[0]]
}
方法三：线段树
class Solution {
class Node {
int l, r, val;
Node (int _l, int _r) {
l = _l; r = _r;
}
}
void build(int u, int l, int r) {
tr[u] = new Node(l, r);
if (l == r) return ;
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
}
void update(int u, int x, int v) {
if (tr[u].l == x && tr[u].r == x) {
tr[u].val = Math.max(tr[u].val, v);
return ;
}
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) update(u << 1, x, v);
else update(u << 1 | 1, x, v);
pushup(u);
}
int query(int u, int l, int r) {
if (l <= tr[u].l && tr[u].r <= r) return tr[u].val;
int mid = tr[u].l + tr[u].r >> 1, ans = 0;
if (l <= mid) ans = query(u << 1, l, r);
if (r > mid) ans = Math.max(ans, query(u << 1 | 1, l, r));
return ans;
}
void pushup(int u) {
tr[u].val = Math.max(tr[u << 1].val, tr[u << 1 | 1].val);
}
Node[] tr = new Node[4010];
int[] hash = new int[1010];
public TreeNode constructMaximumBinaryTree(int[] nums) {
int n = nums.length;
build(1, 1, n);
for (int i = 0; i < n; i++) {
hash[nums[i]] = i + 1;
update(1, i + 1, nums[i]);
}
return dfs(nums, 1, n);
}
TreeNode dfs(int[] nums, int l, int r) {
if (l > r) return null;
int val = query(1, l, r), idx = hash[val];
TreeNode ans = new TreeNode(val);
ans.left = dfs(nums, l, idx - 1);
ans.right = dfs(nums, idx + 1, r);
return ans;
}
}