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)booldfs=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)boolpre:=math.MinIntdfs=func(root *TreeNode)bool{if root==nil{return true}if !dfs(root.Left)||root.Val<=pre{return false}pre=root.Valreturn 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.Valif 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)boolvar node *TreeNodepre:=math.MinIntflag:=falsedfs=func(root *TreeNode)bool{if root==nil||flag{return true}if !dfs(root.Left)||pre>=root.Val{return false}if root.Val==val{node=rootreturn true}pre=root.Valreturn 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:=0dfs=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.Valif 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.Vals:=0if 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.MinIntans:=math.MaxIntvar dfs func(root *TreeNode)booldfs=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.Valreturn 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.MaxIntpre:=math.MinInt/2var dfs func(*TreeNode)dfs=func(node *TreeNode){if node==nil{return}dfs(node.Left)ans=min(ans,node.Val-pre)pre=node.Valdfs(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,-1j,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:=1pre:=math.MinIntmax_len:=1mp:=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.Valdfs(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:=1pre:=math.MinIntmax_len:=1mp:=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.Valdfs(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:=1pre:=math.MinIntmax_len:=1ans:=[]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_lenans=[]int{root.Val}}pre=root.Valdfs(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.MinIntnum:=0dfs=func(root *TreeNode){if root==nil{return}dfs(root.Left)if pre!=root.Val{k--if k==0{num=root.Valreturn }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:=0dfs=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)intdfs=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)boolvar getSum func(root *TreeNode)intvar 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:=0dfs=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)boolvar getSum func(root *TreeNode)intvar 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:=0dfs=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 *TreeNodestart intend int
}
func maxSumBST(root *TreeNode) int {var isBST func(root *TreeNode,left,right int)boolvar getSum func(root *TreeNode)intmp:=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:=0dfs=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:=0dfs=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.Valif x<=lMax||x>=rMin{return math.MinInt,math.MaxInt,0}s:=lSum+rSum+xans=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)*TreeNodedfs=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)*TreeNodedfs=func(inL,inR,postL,postR int)*TreeNode{if postL==postR{return nil}leftSize:=index[postorder[postR-1]]-inLleft:=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])+1left:=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)*TreeNodedfs=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+1left:=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)*TreeNodedfs=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
}