645 最大二叉树
func constructMaximumBinaryTree(nums []int) *TreeNode {
// 思路，算法思路基本等同于通过中序前序构造二叉树
// 1， 取最大值作为根节点
// 2， 切割数组
// 3， 递归左右子树
if len(nums) == 0 {
return nil
}
// 切割数组取最大值
max, left, right := getmax(nums)
var root = &TreeNode{max, nil, nil}
if len(nums) == 1{
return root
}
// 递归左右子树
root.Left = constructMaximumBinaryTree(left)
root.Right = constructMaximumBinaryTree(right)
return root
}
func getmax(nums []int) (int, []int, []int) {
var max int
var index int
var left, right []int
for idx, num := range nums {
if num >= max {
max = num
index = idx
}
}
left = nums[0: index]
if index + 1 <= len(nums) - 1 {
right = nums[index + 1: len(nums)]
}
return max, left, right
}
617 合并二叉树
func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
// 思路，递归前序遍历构造二叉树
if root1 == nil && root2 == nil {
return nil
}
if root1 == nil && root2 != nil {
return root2
}
if root1 != nil && root2 == nil {
return root1
}
// 单次递归逻辑前序，根左右
var root = &TreeNode{root1.Val + root2.Val, nil, nil}
root.Left = mergeTrees(root1.Left, root2.Left)
root.Right = mergeTrees(root1.Right, root2.Right)
return root
}
// 递归秒杀，层序思路大致为，分别遍历两棵树，然后对应节点相构建新的节点加入新队列，然后最终根据队列输出就是新的树
二叉搜索树（Binary Search Tree, 简称 BST）
二叉搜索树是一种特殊的二叉树，它具有以下性质：
-
节点值的排列：
- 对于每一个节点 ( n )：
- 节点 ( n ) 的左子树中的所有节点的值都小于 ( n ) 的值。
- 节点 ( n ) 的右子树中的所有节点的值都大于 ( n ) 的值。
- 对于每一个节点 ( n )：
-
递归性质：
- 每个节点的左子树和右子树也都是二叉搜索树。
这种结构使得在二叉搜索树中进行查找、插入和删除操作非常高效，平均时间复杂度为 ( O(\log n) )（在平衡的情况下）。
二叉搜索树的性质
- 查找：从根节点开始，如果要查找的值小于当前节点的值，则递归地在左子树中查找；如果大于当前节点的值，则在右子树中查找。
- 插入：从根节点开始，根据值的大小决定插入到左子树还是右子树的适当位置。
- 删除：分三种情况：
- 删除的节点是叶子节点：直接删除。
- 删除的节点只有一个子节点：用该子节点替代被删除的节点。
- 删除的节点有两个子节点：找到该节点的中序后继或中序前驱，用后继或前驱替代被删除的节点，然后删除后继或前驱。
二叉搜索树的示例
假设我们有一个包含以下值的二叉搜索树：5, 3, 7, 2, 4, 6, 8。
构建的二叉搜索树如下：
5
/ \
3 7
/ \ / \
2 4 6 8
// TreeNode 定义二叉搜索树节点
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
// Insert 插入一个值到二叉搜索树
func (t *TreeNode) Insert(val int) {
if val < t.Val {
if t.Left == nil {
t.Left = &TreeNode{Val: val}
} else {
t.Left.Insert(val)
}
} else {
if t.Right == nil {
t.Right = &TreeNode{Val: val}
} else {
t.Right.Insert(val)
}
}
}
// Search 在二叉搜索树中查找一个值
func (t *TreeNode) Search(val int) *TreeNode {
if t == nil || t.Val == val {
return t
}
if val < t.Val {
return t.Left.Search(val)
}
return t.Right.Search(val)
}
// Delete 从二叉搜索树中删除一个值
func (t *TreeNode) Delete(val int) *TreeNode {
if t == nil {
return nil
}
if val < t.Val {
t.Left = t.Left.Delete(val)
} else if val > t.Val {
t.Right = t.Right.Delete(val)
} else {
// 找到要删除的节点
if t.Left == nil {
return t.Right
} else if t.Right == nil {
return t.Left
}
// 有两个子节点，找到中序后继
minRight := t.Right
for minRight.Left != nil {
minRight = minRight.Left
}
t.Val = minRight.Val
t.Right = t.Right.Delete(minRight.Val)
}
return t
}
700 二叉树搜索
func searchBST(root *TreeNode, val int) *TreeNode {
// 递归思路，如果根节点大于val，递归右子树，如果小于val，递归左子树，如果等于，返回root
if root == nil {
return nil
}
if root.Val == val {
return root
}
// 单次递归逻辑
if root.Val < val {
return searchBST(root.Right, val)
}
if root.Val > val {
return searchBST(root.Left, val)
}
return nil
}
// 递归秒杀
98 验证二叉搜索树
func isValidBST(root *TreeNode) bool {
// 迭代法思路，中序遍历二叉搜索树得到的数组是单调递增的
if root == nil {
return true
}
var res []int
inorder(root, &res)
return checkOrder(res)
}
func inorder(root *TreeNode, res *[]int) {
if root == nil {
return
}
inorder(root.Left, res)
*res = append(*res, root.Val)
inorder(root.Right, res)
}
func checkOrder(nums []int)bool {
for i := 0; i < len(nums)-1; i++ {
if nums[i] >= nums[i+1] {
return false
}
}
return true
}
var prev *TreeNode
func isValidBST(root *TreeNode) bool {
// 递归方法，思路同样是中序遍历得到的结果是有序的，所以对于每一层递归，上一个节点值小于下一个节点值
prev = nil // tmd 使用全局变量一定要记得在函数中重新归零，不然多次测试可能会互相修改，出现意料之外的错误
return isValidBSTHelper(root)
}
func isValidBSTHelper(root *TreeNode) bool {
if root == nil {
return true
}
// 左子树
left := isValidBSTHelper(root.Left)
// 当前节点
if prev != nil && prev.Val >= root.Val {
return false
}
prev = root
// 右子树
right := isValidBSTHelper(root.Right)
return left && right
}