golang算法二叉搜索树
98. 验证二叉搜索树
给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下:
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:root = [2,1,3]
输出:true
示例 2:
输入:root = [5,1,4,null,null,3,6]
输出:false
解释:根节点的值是 5 ,但是右子节点的值是 4 。
提示:
树中节点数目范围在[1, 104] 内
-231 <= Node.val <= 231 - 1
前序
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isValidBST(root *TreeNode) bool {
var dfs func(root *TreeNode,start,end int)bool
dfs=func(root *TreeNode,start,end int)bool{
if root==nil{
return true
}
return start<root.Val&&root.Val<end&&dfs(root.Left,start,root.Val)&&dfs(root.Right,root.Val,end)
}
return dfs(root,math.MinInt,math.MaxInt)
}
中序
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isValidBST(root *TreeNode) bool {
var dfs func(root *TreeNode)bool
pre:=math.MinInt
dfs=func(root *TreeNode)bool{
if root==nil{
return true
}
if !dfs(root.Left)||root.Val<=pre{
return false
}
pre=root.Val
return dfs(root.Right)
}
return dfs(root)
}
后序
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isValidBST(root *TreeNode) bool {
var dfs func(root *TreeNode)(int,int)
dfs=func(root *TreeNode)(int,int){
if root==nil{
return math.MaxInt,math.MinInt
}
lMin,lMax:=dfs(root.Left)
rMin,rMax:=dfs(root.Right)
x:=root.Val
if x<=lMax||x>=rMin{
return math.MinInt,math.MaxInt
}
return min(lMin,x),max(rMax,x)
}
_,mx:=dfs(root)
return mx!=math.MaxInt
}
700. 二叉搜索树中的搜索
给定二叉搜索树(BST)的根节点 root 和一个整数值 val。
你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 null 。
示例 1:
输入:root = [4,2,7,1,3], val = 2
输出:[2,1,3]
示例 2:
输入:root = [4,2,7,1,3], val = 5
输出:[]
提示:
树中节点数在 [1, 5000] 范围内
1 <= Node.val <= 107
root 是二叉搜索树
1 <= val <= 107
```cpp
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func searchBST(root *TreeNode, val int) *TreeNode {
if root==nil{
return nil
}
l:=searchBST(root.Left,val)
if root.Val==val{
return root
}
r:=searchBST(root.Right,val)
if l!=nil{
return l
}else{
return r
}
}
## 哈哈哈哈哈哈太复杂了
```cpp
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func searchBST(root *TreeNode, val int) *TreeNode {
var dfs func(root *TreeNode)bool
var node *TreeNode
pre:=math.MinInt
flag:=false
dfs=func(root *TreeNode)bool{
if root==nil||flag{
return true
}
if !dfs(root.Left)||pre>=root.Val{
return false
}
if root.Val==val{
node=root
return true
}
pre=root.Val
return dfs(root.Right)
}
dfs(root)
return node
}
938. 二叉搜索树的范围和
给定二叉搜索树的根结点 root,返回值位于范围 [low, high] 之间的所有结点的值的和。
示例 1:
输入:root = [10,5,15,3,7,null,18], low = 7, high = 15
输出:32
示例 2:
输入:root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
输出:23
提示:
树中节点数目在范围 [1, 2 * 104] 内
1 <= Node.val <= 105
1 <= low <= high <= 105
所有 Node.val 互不相同
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func rangeSumBST(root *TreeNode, low int, high int) int {
var dfs func(root *TreeNode)
ans:=0
dfs=func(root *TreeNode){
if root==nil{
return
}
if root.Val>=low&&root.Val<=high{
ans+=root.Val
}
if root.Val>high{
dfs(root.Left)
}else if root.Val<low{
dfs(root.Right)
}else{
dfs(root.Left)
dfs(root.Right)
}
}
dfs(root)
return ans
}
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func rangeSumBST(root *TreeNode, low int, high int) int {
if root ==nil{
return 0
}
x:=root.Val
if x>high{
return rangeSumBST(root.Left,low,high)
}
if x<low{
return rangeSumBST(root.Right,low,high)
}
return x+rangeSumBST(root.Left,low,high)+rangeSumBST(root.Right,low,high)
}
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func rangeSumBST(root *TreeNode, low int, high int) int {
if root==nil{
return 0
}
x:=root.Val
s:=0
if low<=x&&x<=high{
s=x
}
if x>low{
s+=rangeSumBST(root.Left,low,high)
}
if x<high{
s+=rangeSumBST(root.Right,low,high)
}
return s
}
530. 二叉搜索树的最小绝对差
给你一个二叉搜索树的根节点 root ,返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数,其数值等于两值之差的绝对值。
示例 1:
输入:root = [4,2,6,1,3]
输出:1
示例 2:
输入:root = [1,0,48,null,null,12,49]
输出:1
提示:
树中节点的数目范围是 [2, 104]
0 <= Node.val <= 105
注意:本题与 783 https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/ 相同
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func getMinimumDifference(root *TreeNode) int {
pre:=math.MinInt
ans:=math.MaxInt
var dfs func(root *TreeNode)bool
dfs=func(root *TreeNode)bool{
if root==nil{
return true
}
if !dfs(root.Left)||pre>=root.Val{
return false
}
if ans>root.Val-pre&&pre!=math.MinInt{
ans=root.Val-pre
}
pre=root.Val
return dfs(root.Right)
}
dfs(root)
return ans
}
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func getMinimumDifference(root *TreeNode) int {
ans:=math.MaxInt
pre:=math.MinInt/2
var dfs func(*TreeNode)
dfs=func(node *TreeNode){
if node==nil{
return
}
dfs(node.Left)
ans=min(ans,node.Val-pre)
pre=node.Val
dfs(node.Right)
}
dfs(root)
return ans
}
2476. 二叉搜索树最近节点查询
给你一个 二叉搜索树 的根节点 root ,和一个由正整数组成、长度为 n 的数组 queries 。
请你找出一个长度为 n 的 二维 答案数组 answer ,其中 answer[i] = [mini, maxi] :
mini 是树中小于等于 queries[i] 的 最大值 。如果不存在这样的值,则使用 -1 代替。
maxi 是树中大于等于 queries[i] 的 最小值 。如果不存在这样的值,则使用 -1 代替。
返回数组 answer 。
示例 1 :
输入:root = [6,2,13,1,4,9,15,null,null,null,null,null,null,14], queries = [2,5,16]
输出:[[2,2],[4,6],[15,-1]]
解释:按下面的描述找出并返回查询的答案:
- 树中小于等于 2 的最大值是 2 ,且大于等于 2 的最小值也是 2 。所以第一个查询的答案是 [2,2] 。
- 树中小于等于 5 的最大值是 4 ,且大于等于 5 的最小值是 6 。所以第二个查询的答案是 [4,6] 。
- 树中小于等于 16 的最大值是 15 ,且大于等于 16 的最小值不存在。所以第三个查询的答案是 [15,-1] 。
示例 2 :
输入:root = [4,null,9], queries = [3]
输出:[[-1,4]]
解释:树中不存在小于等于 3 的最大值,且大于等于 3 的最小值是 4 。所以查询的答案是 [-1,4] 。
提示:
树中节点的数目在范围 [2, 105] 内
1 <= Node.val <= 106
n == queries.length
1 <= n <= 105
1 <= queries[i] <= 106
暴力(因为是无序)(超时)
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func closestNodes(root *TreeNode, queries []int) [][]int {
var dfs func(root *TreeNode)
ans:=[][]int{}
for i:=0;i<len(queries);i++{
ans=append(ans,[]int{math.MinInt,math.MaxInt})
}
dfs=func(root *TreeNode){
if root==nil{
return
}
dfs(root.Left)
for i:=0;i<len(queries);i++{
if root.Val<=queries[i]{
ans[i][0]=max(root.Val,ans[i][0])
}
if root.Val>=queries[i]{
ans[i][1]=min(ans[i][1],root.Val)
}
}
dfs(root.Right)
}
dfs(root)
for i:=0;i<len(queries);i++{
if ans[i][0]==math.MinInt{
ans[i][0]=-1
}
if ans[i][1]==math.MaxInt{
ans[i][1]=-1
}
}
return ans
}
map+slices(超时)
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func closestNodes(root *TreeNode, queries []int) [][]int {
var dfs func(root *TreeNode)
mp_min:=map[int][]int{}
mp_max:=map[int][]int{}
for i:=0;i<len(queries);i++{
mp_min[queries[i]]=append(mp_min[queries[i]],i)
mp_max[queries[i]]=append(mp_max[queries[i]],i)
}
ans:=[][]int{}
for i:=0;i<len(queries);i++{
ans=append(ans,[]int{math.MinInt,math.MaxInt})
}
dfs=func(root *TreeNode){
if root==nil{
return
}
dfs(root.Left)
for k,v:=range mp_min{
if root.Val<=k{
for _,vv:=range v{
ans[vv][0]=max(root.Val,ans[vv][0])
}
}else{
delete(mp_min,k)
}
}
for k,v:=range mp_max{
if root.Val>=k{
for _,vv:=range v{
ans[vv][1]=root.Val
}
delete(mp_max,k)
}
}
dfs(root.Right)
}
dfs(root)
for i:=0;i<len(queries);i++{
if ans[i][0]==math.MinInt{
ans[i][0]=-1
}
if ans[i][1]==math.MaxInt{
ans[i][1]=-1
}
}
return ans
}
中序遍历+二分
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func closestNodes(root *TreeNode, queries []int) [][]int {
a:=[]int{}
var dfs func(*TreeNode)
dfs=func(node *TreeNode){
if node==nil{
return
}
dfs(node.Left)
a=append(a,node.Val)
dfs(node.Right)
}
dfs(root)
ans:=make([][]int,len(queries))
for i,q:=range queries{
mn,mx:=-1,-1
j,ok:=slices.BinarySearch(a,q)
if j<len(a){
mx=a[j]
}
if !ok{
j--
}
if j>=0{
mn=a[j]
}
ans[i]=[]int{mn,mx}
}
return ans
}
501. 二叉搜索树中的众数
给你一个含重复值的二叉搜索树(BST)的根节点 root ,找出并返回 BST 中的所有 众数(即,出现频率最高的元素)。
如果树中有不止一个众数,可以按 任意顺序 返回。
假定 BST 满足如下定义:
结点左子树中所含节点的值 小于等于 当前节点的值
结点右子树中所含节点的值 大于等于 当前节点的值
左子树和右子树都是二叉搜索树
示例 1:
输入:root = [1,null,2,2]
输出:[2]
示例 2:
输入:root = [0]
输出:[0]
提示:
树中节点的数目在范围 [1, 104] 内
-105 <= Node.val <= 105
进阶:你可以不使用额外的空间吗?(假设由递归产生的隐式调用栈的开销不被计算在内)
重复添加修改下一个
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func findMode(root *TreeNode) []int {
var dfs func(root *TreeNode)
cur_len:=1
pre:=math.MinInt
max_len:=1
mp:=map[int][]int{}
dfs=func(root *TreeNode){
if root==nil{
return
}
dfs(root.Left)
if root.Val==pre{
cur_len++
if cur_len>max_len{
max_len=cur_len
}
if _,ok:=mp[cur_len];!ok{
mp[cur_len]=[]int{root.Val}
}else{
mp[cur_len]=append(mp[cur_len],root.Val)
}
}else{
if _,ok:=mp[cur_len];!ok{
mp[cur_len]=[]int{root.Val}
}else{
mp[cur_len]=append(mp[cur_len],root.Val)
}
cur_len=1
}
pre=root.Val
dfs(root.Right)
}
dfs(root)
return mp[max_len]
}
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func findMode(root *TreeNode) []int {
var dfs func(root *TreeNode)
cur_len:=1
pre:=math.MinInt
max_len:=1
mp:=map[int][]int{}
dfs=func(root *TreeNode){
if root==nil{
return
}
dfs(root.Left)
if root.Val==pre{
cur_len++
if cur_len>max_len{
max_len=cur_len
}
if _,ok:=mp[cur_len];!ok{
mp[cur_len]=[]int{root.Val}
}else{
mp[cur_len]=append(mp[cur_len],root.Val)
}
}else{
if cur_len==1{
if _,ok:=mp[cur_len];!ok{
mp[cur_len]=[]int{root.Val}
}else{
mp[cur_len]=append(mp[cur_len],root.Val)
}
}
cur_len=1
}
pre=root.Val
dfs(root.Right)
}
dfs(root)
return mp[max_len]
}
简化一些
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func findMode(root *TreeNode) []int {
var dfs func(root *TreeNode)
cur_len:=1
pre:=math.MinInt
max_len:=1
ans:=[]int{}
dfs=func(root *TreeNode){
if root==nil{
return
}
dfs(root.Left)
if root.Val==pre{
cur_len++
}else{
cur_len=1
}
if cur_len==max_len{
ans=append(ans,root.Val)
}
if cur_len>max_len{
max_len=cur_len
ans=[]int{root.Val}
}
pre=root.Val
dfs(root.Right)
}
dfs(root)
return ans
}
230. 二叉搜索树中第 K 小的元素
给定一个二叉搜索树的根节点 root ,和一个整数 k ,请你设计一个算法查找其中第 k 小的元素(从 1 开始计数)。
示例 1:
输入:root = [3,1,4,null,2], k = 1
输出:1
示例 2:
输入:root = [5,3,6,2,4,null,null,1], k = 3
输出:3
提示:
树中的节点数为 n 。
1 <= k <= n <= 104
0 <= Node.val <= 104
进阶:如果二叉搜索树经常被修改(插入/删除操作)并且你需要频繁地查找第 k 小的值,你将如何优化算法?
记录答案
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func kthSmallest(root *TreeNode, k int) int {
var dfs func(root *TreeNode)
pre:=math.MinInt
num:=0
dfs=func(root *TreeNode){
if root==nil{
return
}
dfs(root.Left)
if pre!=root.Val{
k--
if k==0{
num=root.Val
return
}
pre=root.Val
}
dfs(root.Right)
}
dfs(root)
return num
}
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func kthSmallest(root *TreeNode, k int) int {
var dfs func(root *TreeNode)
num:=0
dfs=func(root *TreeNode){
if root==nil{
return
}
dfs(root.Left)
k--
if k==0{
num=root.Val
}
dfs(root.Right)
}
dfs(root)
return num
}
不记录答案 + 提前返回
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func kthSmallest(root *TreeNode, k int) int {
var dfs func(root *TreeNode)int
dfs=func(root *TreeNode)int{
if root==nil{
return -1
}
leftRes:=dfs(root.Left)
if leftRes!=-1{
return leftRes
}
k--
if k==0{
return root.Val
}
return dfs(root.Right)
}
return dfs(root)
}
1373. 二叉搜索子树的最大键值和
给你一棵以 root 为根的 二叉树 ,请你返回 任意 二叉搜索子树的最大键值和。
二叉搜索树的定义如下:
任意节点的左子树中的键值都 小于 此节点的键值。
任意节点的右子树中的键值都 大于 此节点的键值。
任意节点的左子树和右子树都是二叉搜索树。
示例 1:
输入:root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]
输出:20
解释:键值为 3 的子树是和最大的二叉搜索树。
示例 2:
输入:root = [4,3,null,1,2]
输出:2
解释:键值为 2 的单节点子树是和最大的二叉搜索树。
示例 3:
输入:root = [-4,-2,-5]
输出:0
解释:所有节点键值都为负数,和最大的二叉搜索树为空。
示例 4:
输入:root = [2,1,3]
输出:6
示例 5:
输入:root = [5,4,8,3,null,6,3]
输出:7
提示:
每棵树有 1 到 40000 个节点。
每个节点的键值在 [-4 * 10^4 , 4 * 10^4] 之间。
出错,忽略了子节点构成的二叉搜索树比父节点构成的二叉搜索树数值和更大
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func maxSumBST(root *TreeNode) int {
var isBST func(root *TreeNode,left,right int)bool
var getSum func(root *TreeNode)int
var dfs func(root *TreeNode)
isBST=func(root *TreeNode,left,right int)bool{
if root==nil{
return true
}
return root.Val>left&&root.Val<right&&isBST(root.Left,left,root.Val)&&isBST(root.Right,root.Val,right)
}
getSum=func(root *TreeNode)int{
if root==nil{
return 0
}
return root.Val+getSum(root.Left)+getSum(root.Right)
}
ans:=0
dfs=func(root *TreeNode){
if root==nil{
return
}
if isBST(root,math.MinInt,math.MaxInt){
ans=max(ans,getSum(root))
}
dfs(root.Left)
dfs(root.Right)
}
dfs(root)
return ans
}
超时
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func maxSumBST(root *TreeNode) int {
var isBST func(root *TreeNode,left,right int)bool
var getSum func(root *TreeNode)int
var dfs func(root *TreeNode)
isBST=func(root *TreeNode,left,right int)bool{
if root==nil{
return true
}
return root.Val>left&&root.Val<right&&isBST(root.Left,left,root.Val)&&isBST(root.Right,root.Val,right)
}
getSum=func(root *TreeNode)int{
if root==nil{
return 0
}
return root.Val+getSum(root.Left)+getSum(root.Right)
}
ans:=0
dfs=func(root *TreeNode){
if root==nil{
return
}
if isBST(root,math.MinInt,math.MaxInt){
ans=max(ans,getSum(root))
}
dfs(root.Left)
dfs(root.Right)
}
dfs(root)
return ans
}
记忆数组
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
type bst struct{
root *TreeNode
start int
end int
}
func maxSumBST(root *TreeNode) int {
var isBST func(root *TreeNode,left,right int)bool
var getSum func(root *TreeNode)int
mp:=map[*TreeNode]int{}
mp_bst:=map[bst]bool{}
var dfs func(root *TreeNode)
isBST=func(root *TreeNode,left,right int)bool{
if root==nil{
return true
}
if v,ok:=mp_bst[bst{root,left,right}];ok{
return v
}
mp_bst[bst{root,left,right}]=root.Val>left&&root.Val<right&&isBST(root.Left,left,root.Val)&&isBST(root.Right,root.Val,right)
return mp_bst[bst{root,left,right}]
}
getSum=func(root *TreeNode)int{
if root==nil{
return 0
}
if v,ok:=mp[root];ok{
return v
}
mp[root]=root.Val+getSum(root.Left)+getSum(root.Right)
return mp[root]
}
ans:=0
dfs=func(root *TreeNode){
if root==nil{
return
}
if isBST(root,math.MinInt,math.MaxInt){
ans=max(ans,getSum(root))
}
dfs(root.Left)
dfs(root.Right)
}
dfs(root)
return ans
}
后序遍历
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func maxSumBST(root *TreeNode) int {
var dfs func(root *TreeNode)(int,int,int)
ans:=0
dfs=func(root *TreeNode)(int,int,int){
if root==nil{
return math.MaxInt,math.MinInt,0
}
lMin,lMax,lSum:=dfs(root.Left)
rMin,rMax,rSum:=dfs(root.Right)
x:=root.Val
if x<=lMax||x>=rMin{
return math.MinInt,math.MaxInt,0
}
s:=lSum+rSum+x
ans=max(ans,s)
return min(lMin,x),max(rMax,x),s
}
dfs(root)
return ans
}
105. 从前序与中序遍历序列构造二叉树
给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。
示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
示例 2:
输入: preorder = [-1], inorder = [-1]
输出: [-1]
提示:
1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 均 无重复 元素
inorder 均出现在 preorder
preorder 保证 为二叉树的前序遍历序列
inorder 保证 为二叉树的中序遍历序列
递归
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func buildTree(preorder []int, inorder []int) *TreeNode {
n:=len(preorder)
if n==0{
return nil
}
leftSize:=slices.Index(inorder,preorder[0])//左子树
left:=buildTree(preorder[1:1+leftSize],inorder[:leftSize])
right:=buildTree(preorder[1+leftSize:],inorder[1+leftSize:])
return &TreeNode{preorder[0],left,right}
}
优化
上面的写法有两个优化点:
1.用一个哈希表(或者数组)预处理 inorder 每个元素的下标,这样就可以 O(1) 查到 preorder[0] 在 inorder 的位置,从而 O(1) 知道左子树的大小。
2.把递归参数改成子数组下标区间(左闭右开区间)的左右端点,从而避免复制数组。
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func buildTree(preorder []int, inorder []int) *TreeNode {
n:=len(preorder)
index:=make(map[int]int,n)
for i,x:=range inorder{
index[x]=i
}
var dfs func(int,int,int,int)*TreeNode
dfs=func(preL,preR,inL,inR int)*TreeNode{
if preL==preR{//空节点
return nil
}
leftSize:=index[preorder[preL]]-inL//左子树的大小
left:=dfs(preL+1,preL+1+leftSize,inL,inL+leftSize)
right:=dfs(preL+1+leftSize,preR,inL+1+leftSize,inR)
return &TreeNode{preorder[preL],left,right}
}
return dfs(0,n,0,n)
}
106. 从中序与后序遍历序列构造二叉树
给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。
示例 1:
输入:inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出:[3,9,20,null,null,15,7]
示例 2:
输入:inorder = [-1], postorder = [-1]
输出:[-1]
提示:
1 <= inorder.length <= 3000
postorder.length == inorder.length
-3000 <= inorder[i], postorder[i] <= 3000
inorder 和 postorder 都由 不同 的值组成
postorder 中每一个值都在 inorder 中
inorder 保证是树的中序遍历
postorder 保证是树的后序遍历
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func buildTree(inorder []int, postorder []int) *TreeNode {
if len(inorder)==0{
return nil
}
leftSize:=slices.Index(inorder,postorder[len(inorder)-1])
left:=buildTree(inorder[:leftSize],postorder[:leftSize])
right:=buildTree(inorder[leftSize+1:],postorder[leftSize:len(postorder)-1])
return &TreeNode{postorder[len(inorder)-1],left,right}
}
优化
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func buildTree(inorder []int, postorder []int) *TreeNode {
n:=len(postorder)
index:=make(map[int]int,n)
if n==0{
return nil
}
for i,x:=range inorder{
index[x]=i
}
var dfs func(int,int,int,int)*TreeNode
dfs=func(inL,inR,postL,postR int)*TreeNode{
if postL==postR{
return nil
}
leftSize:=index[postorder[postR-1]]-inL
left:=dfs(inL,inL+leftSize,postL,postL+leftSize)
right:=dfs(inL+leftSize+1,inR,postL+leftSize,postR-1)
return &TreeNode{postorder[postR-1],left,right}
}
return dfs(0,n,0,n)
}
889. 根据前序和后序遍历构造二叉树
给定两个整数数组,preorder 和 postorder ,其中 preorder 是一个具有 无重复 值的二叉树的前序遍历,postorder 是同一棵树的后序遍历,重构并返回二叉树。
如果存在多个答案,您可以返回其中 任何 一个。
示例 1:
输入:preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
输出:[1,2,3,4,5,6,7]
示例 2:
输入: preorder = [1], postorder = [1]
输出: [1]
提示:
1 <= preorder.length <= 30
1 <= preorder[i] <= preorder.length
preorder 中所有值都 不同
postorder.length == preorder.length
1 <= postorder[i] <= postorder.length
postorder 中所有值都 不同
保证 preorder 和 postorder 是同一棵二叉树的前序遍历和后序遍历
题目说,如果存在多个答案,我们可以返回其中任何一个。那么不妨规定:无论什么情况,在前序遍历中,preorder[1] 都是左子树的根节点值。
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func constructFromPrePost(preorder []int, postorder []int) *TreeNode {
n:=len(preorder)
if n==0{
return nil
}
if n==1{
return &TreeNode{Val:preorder[0]}
}
leftSize:=slices.Index(postorder,preorder[1])+1
left:=constructFromPrePost(preorder[1:1+leftSize],postorder[:leftSize])
right:=constructFromPrePost(preorder[1+leftSize:],postorder[leftSize:n-1])
return &TreeNode{preorder[0],left,right}
}
优化
灵茶山艾府上面的写法有两个优化点:
1.用一个哈希表(或者数组)预处理 postorder 每个元素的下标,这样就可以 O(1) 查到 preorder[1] 在 postorder 的位置,从而 O(1) 知道左子树的大小。
2.把递归参数改成子数组下标区间(左闭右开区间)的左右端点,从而避免复制数组。
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func constructFromPrePost(preorder []int, postorder []int) *TreeNode {
n:=len(preorder)
index:=make([]int,n+1)
for i,x:=range postorder{
index[x]=i
}
var dfs func(int,int,int)*TreeNode
dfs=func(preL,preR,postL int)*TreeNode{
if preL==preR{//空节点
return nil
}
if preL+1==preR{//页子节点
return &TreeNode{Val:preorder[preL]}
}
leftSize:=index[preorder[preL+1]]-postL+1
left:=dfs(preL+1,preL+1+leftSize,postL)
right:=dfs(preL+1+leftSize,preR,postL+leftSize)
return &TreeNode{preorder[preL],left,right}
}
return dfs(0,n,0)
}
1110. 删点成林
给出二叉树的根节点 root,树上每个节点都有一个不同的值。
如果节点值在 to_delete 中出现,我们就把该节点从树上删去,最后得到一个森林(一些不相交的树构成的集合)。
返回森林中的每棵树。你可以按任意顺序组织答案。
示例 1:
输入:root = [1,2,3,4,5,6,7], to_delete = [3,5]
输出:[[1,2,null,4],[6],[7]]
示例 2:
输入:root = [1,2,4,null,3], to_delete = [3]
输出:[[1,2,4]]
提示:
树中的节点数最大为 1000。
每个节点都有一个介于 1 到 1000 之间的值,且各不相同。
to_delete.length <= 1000
to_delete 包含一些从 1 到 1000、各不相同的值。
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func delNodes(root *TreeNode, to_delete []int) []*TreeNode {
ans:=[]*TreeNode{}
mp:=map[int]bool{}
for i:=0;i<len(to_delete);i++{
mp[to_delete[i]]=true
}
var dfs func(pre,root *TreeNode)
dfs=func(pre,root *TreeNode){
if root==nil{
return
}
if mp[root.Val]{
if root.Left!=nil{
if _,ok:=mp[root.Left.Val];!ok{
ans=append(ans,root.Left)
}
}
if root.Right!=nil{
if _,ok:=mp[root.Right.Val];!ok{
ans=append(ans,root.Right)
}
}
if pre.Left==root{
pre.Left=nil
}else if pre.Right==root{
pre.Right=nil
}
}
dfs(root,root.Left)
dfs(root,root.Right)
}
if mp[root.Val]{
if root.Left!=nil{
if _,ok:=mp[root.Left.Val];!ok{
ans=append(ans,root.Left)
}
}
if root.Right!=nil{
if _,ok:=mp[root.Right.Val];!ok{
ans=append(ans,root.Right)
}
}
dfs(root,root.Left)
dfs(root,root.Right)
}else{
ans=append(ans,root)
dfs(nil,root)
}
return ans
}
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func delNodes(root *TreeNode, to_delete []int) []*TreeNode {
ans:=[]*TreeNode{}
set:=make(map[int]struct{},len(to_delete))
for _,x:=range to_delete{
set[x]=struct{}{}
}
var dfs func(*TreeNode)*TreeNode
dfs=func(node *TreeNode)*TreeNode{
if node==nil{
return nil
}
node.Left=dfs(node.Left)
node.Right=dfs(node.Right)
if _,ok:=set[node.Val];!ok{
return node
}
if node.Left!=nil{
ans=append(ans,node.Left)
}
if node.Right!=nil{
ans=append(ans,node.Right)
}
return nil
}
if dfs(root)!=nil{
ans=append(ans,root)
}
return ans
}