【2022-08-30每日一题】998. 最大二叉树 II
2022-08-30
2分钟阅读时长
2022-08-30每日一题：998. 最大二叉树 II
- 难度：Medium
- 标签：树 、 二叉树
最大树 定义：一棵树，并满足：其中每个节点的值都大于其子树中的任何其他值。
给你最大树的根节点 root 和一个整数 val 。
就像 之前的问题 那样，给定的树是利用 Construct(a) 例程从列表 a（root = Construct(a)）递归地构建的：
- 如果
a为空，返回null。 - 否则，令
a[i]作为a的最大元素。创建一个值为a[i]的根节点root。 root的左子树将被构建为Construct([a[0], a[1], ..., a[i - 1]])。root的右子树将被构建为Construct([a[i + 1], a[i + 2], ..., a[a.length - 1]])。- 返回
root。
请注意，题目没有直接给出 a ，只是给出一个根节点 root = Construct(a) 。
假设 b 是 a 的副本，并在末尾附加值 val。题目数据保证 b 中的值互不相同。
返回 Construct(b) 。
示例 1：
输入：root = [4,1,3,null,null,2], val = 5 输出：[5,4,null,1,3,null,null,2] 解释：a = [1,4,2,3], b = [1,4,2,3,5]
示例 2：
输入：root = [5,2,4,null,1], val = 3 输出：[5,2,4,null,1,null,3] 解释：a = [2,1,5,4], b = [2,1,5,4,3]
示例 3：
输入：root = [5,2,3,null,1], val = 4 输出：[5,2,4,null,1,3] 解释：a = [2,1,5,3], b = [2,1,5,3,4]
提示：
- 树中节点数目在范围
[1, 100]内 1 <= Node.val <= 100- 树中的所有值 互不相同
1 <= val <= 100
官方解法
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func insertIntoMaxTree(root *TreeNode, val int) *TreeNode {
var parent *TreeNode
for cur := root; cur != nil; cur = cur.Right {
if val > cur.Val {
if parent == nil {
return &TreeNode{val, cur, nil}
}
parent.Right = &TreeNode{val, cur, nil}
return root
}
parent = cur
}
parent.Right = &TreeNode{Val: val}
return root
}
复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(1)
宫水三叶
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func insertIntoMaxTree(root *TreeNode, val int) *TreeNode {
node :=&TreeNode{Val: val}
pre, cur := (*TreeNode)(nil), root
for cur != nil && cur.Val > val {
pre, cur = cur, cur.Right
}
if pre == nil {
node.Left = root
return node
}
pre.Right, node.Left = node, cur
return root
}
递归
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func insertIntoMaxTree(root *TreeNode, val int) *TreeNode {
//找到底部
if root == nil {
return &TreeNode{Val: val}
}
//找到大于的节点
if root.Val < val {
return &TreeNode{Val: val, Left: root}
}
//遍历右节点
root.Right = insertIntoMaxTree(root.Right, val)
return root
}