二叉树

理论基础

---

满二叉树

父节点下面 两个子节点都存在

深度为K ， 有2^k-1个结点

完全二叉树

除最底层节点不全，其他层节点都是满的

同时最底层从左往右不能断掉

二叉搜索树

有数值

所有左子树上的节点小于根节点

所有右子树的节点大于根节点

平衡二叉搜索树

在前者的基础上

加一条：左右子树的高度差绝对值不超过1

表现

Definition for a binary tree node.
type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
} 

二叉树的前序遍历

func preorderTraversal(root *TreeNode)[]int{
    vals := make ([]int,0)
    var preorder func(*TreeNode)
    preorder = func(node *TreeNode) {
        if node == nil {
            return
        }
        vals = append(vals, node.Val)
        preorder(node.Left)
        preorder(node.Right)
    }
    preorder(root)
    return vals 
}

注意：这里把函数当作一个类型，非常巧妙

官方答案：

func preorderTraversal(root *TreeNode)(vals []int){
    var preorder func(*TreeNode)
    preorder = func(node *TreeNode) {
        if node == nil {
            return
        }
        vals = append(vals, node.Val)
        preorder(node.Left)
        preorder(node.Right)
    }
    preorder(root)
    return
}

官方文档中的返回值是 vals []int 而不是 []int

这个签名表示vals会默认在函数前var，同时return的时候默认return vals

所以这里函数中的vals 和 return 格外奇怪

迭代法

func preorderTraversal(root *TreeNode)(vals []int){
    stack := []*TreeNode{}  // 表示栈
    node := root
    for node != nil || len(stack)>0{
        for node!=nil{   // 不断地向左遍历
            vals = append(vals,node.Val)
            stack = append(stack,node)
            node = node.Left
        }
        // 遍历完左边后开始右边，但是从右端开始又得从左端开始循环遍历
        node = stack[len(stack)-1].Right
        stack = stack[:len(stack)-1]
    }
    return 
}

就是按照根左右的顺序去遍历，坚持要先将左侧遍历完才能遍历右侧的原则

中序遍历

---

递归的方法和前序遍历一样

func inorderTraversal(root *TreeNode) (res []int) {
    var inorder func(*TreeNode)
    inorder = func(node *TreeNode){
        if node == nil{
            return 
        }
        inorder(node.Left)
        res = append(res,node.Val) 
        inorder(node.Right)
    }
    inorder(root)
    return  
}

迭代的方法和前序遍历一样

func inorderTraversal(root *TreeNode) (res []int){
    stack := []*TreeNode{}
    node := root 
    for node!=nil || len(stack)>0{
        for node!=nil{
            stack = append(stack,node)
            node = node.Left
        }
        node = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        res = append(res,node.Val)
        node = node.Right
    }
    return 
}

==morris==中序遍历

个人感觉==morris==有点回溯的味道，他的操作说粗鄙一点就是牵狗链

正常来说我们想要回溯会使用到递归或者数组的操作，但是这里的回溯是通过指针来实现的

牵狗链的实现方式

• 如果当前节点没有右节点，则把当前节点的右节点变成当前的root,注意是当前的，因为root会改变移动
• 不停地向左节点遍历–>每一层的左节点的右节点指向上一层的root

随便看看：

若当前节点 root 的左子树为空，将当前节点值添加至结果列表 ans 中，并将当前节点更新为 root.right
若当前节点 root 的左子树不为空，找到左子树的最右节点 prev（也即是 root 节点在中序遍历下的前驱节点）：
若前驱节点 prev 的右子树为空，将前驱节点的右子树指向当前节点 root，并将当前节点更新为 root.left。
若前驱节点 prev 的右子树不为空，将当前节点值添加至结果列表 ans 中，然后将前驱节点右子树指向空（即解除 prev 与 root 的指向关系），并将当前节点更新为 root.right。

个人觉得还是画图，如果你还是不清楚，就画个图

func inorderTraversal(root *TreeNode) (res []int) {
	for root != nil {
		if root.Left != nil {
			// pre 节点表示当前 root 节点向左走一步，然后一直向右走至无法走为止的节点
			pre := root.Left
			for pre.Right != nil && pre.Right != root {
				// 有右子树且没有设置过指向 root，则继续向右走
				pre = pre.Right
			}
			if pre.Right == nil {
				// 将 pre 的右指针指向 root，这样后面遍历完左子树 root.Left 后，就能通过这个指向回到 root
				pre.Right = root
				// 遍历左子树
				root = root.Left
			} else { // pre 的右指针已经指向了 root，则表示左子树 root.Left 已经访问完了
				res = append(res, root.Val)
				// 恢复原样
				pre.Right = nil
				// 遍历右子树
				root = root.Right
			}
		} else { // 没有左子树
			res = append(res, root.Val)
			// 若有右子树，则遍历右子树
			// 若没有右子树，则整颗左子树已遍历完，root 会通过之前设置的指向回到这颗子树的父节点
			root = root.Right
		}
	}
	return
}

后序遍历

---

递归：

func postorderTraversal(root *TreeNode) (res []int) {
    var postOrder func(*TreeNode)
    postOrder= func(node *TreeNode){
        if node==nil{
            return 
        }
        postOrder(node.Left)
        postOrder(node.Right)
        res = append(res,node.Val)
    }
    postOrder(root)
    return 
}

迭代

层状遍历

---

func levelOrder(root *TreeNode) [][]int {
    if root == nil {
        return [][]int{}
    }
    
    result := [][]int{}
    queue := []*TreeNode{root}
    
    for len(queue) > 0 {
        levelSize := len(queue)
        level := make([]int, levelSize)
        
        for i := 0; i < levelSize; i++ {
            node := queue[i]
            level[i] = node.Val
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        
        result = append(result, level)
        queue = queue[levelSize:] // 移除已处理的节点
    }
    
    return result
}

使用队列来实现

反转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

递归

func invertTree(root *TreeNode)*TreeNode{
    if root == nil {
        return nil 
    }
    left := invertTree(root.Left)
    right := invertTree(root.Right)
    root.Left = right
    root.Right = left
    return root 
}

迭代

func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    
    // 创建一个新的队列用于存储待处理的节点
    queue := []*TreeNode{}
    queue = append(queue, root)
    
    // 使用循环来遍历和翻转每个节点
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:] // 移除队列头部的节点
        
        // 交换节点的左右子树
        node.Left, node.Right = node.Right, node.Left
        
        // 如果节点的左右子树不为空，则将它们加入队列
        if node.Left != nil {
            queue = append(queue, node.Left)
        }
        if node.Right != nil {
            queue = append(queue, node.Right)
        }
    }
    
    // 返回翻转后的树的根节点
    return root
}

对称二叉树

查看一棵树是否对称

递归

func isSymmetric(root *TreeNode) bool {
    if root == nil {
        return true  
    }

    return dfs(root.Left,root.Right)
}

func dfs(left *TreeNode,right *TreeNode)   bool {
    if left== nil &&right == nil {
        return true 
    }
    if left==nil || right ==nil{
        return false 
    }
    if left.Val!= right.Val{
        return false 
    }
    return dfs(left.Right,right.Left) && dfs(left.Left,right.Right)
}

迭代

迭代的思路和递归的思路一样

其实两者的思路就是—> 对称 —-> 一对子树是相同的

在代码中体现就是

left.Left == right . Right

left.Right == right . Left

func isSymmetric(root *TreeNode) bool {
    if root == nil || (root.Left==nil &&root.Right == nil ){
        return true 
    }

    queue := []*TreeNode{root.Left,root.Right}

    for len(queue) > 0 {
        left := queue[0]
        right := queue[1]
        queue = queue[2:]

        if left == nil && right == nil {
            continue
        }

        if left == nil || right == nil{
            return false
        }

        if left.Val != right.Val{
            return false
        }
        // 一对
        queue = append(queue, left.Left)
        queue = append(queue,right.Right)
        // 另一对
        queue = append(queue,left.Right)
        queue = append(queue,right.Left)
    }

    return true

}

二叉树的最大深度

层状遍历

就是过一层，num++

但是这个方法感觉数层数只是附带品。。。

func maxDepth(root *TreeNode) int {
    if root == nil{
        return 0
    }
    var num int 
    queue := []*TreeNode{root}

    for len(queue)>0{
        lenSize := len(queue)

        for i:=0 ;i<lenSize;i++{
            node := queue[i]
            if node.Left!=nil{
                queue = append(queue,node.Left)
            }
            if node.Right!=nil{
                queue =append(queue,node.Right)
            }
        }
        queue = queue[lenSize:]
        num++
    }

    return num 
}

递归（important）

func maxDepth(root *TreeNode) int {
    if root ==nil {
        return 0
    }

    return max(maxDepth(root.Left),maxDepth(root.Right))+1
}

func max(a,b int) int {
    if a>b {
        return a 
    }
    return b 
}

递归太难了

节点计数

层状遍历

没啥好讲的

func countNodes(root *TreeNode) int {
    if root == nil {
        return 0
    }

    queue := []*TreeNode{root}
    num := 1;
    for len(queue)>0{
        len := len(queue)
        for i:=0 ;i<len;i++{
            if queue[i].Right !=nil {
                num ++;
                queue = append(queue,queue[i].Right)
            }
            if queue[i].Left !=nil {
                num ++;
                queue = append(queue,queue[i].Left)
            }
        }
        queue = queue[len:]
    }

    return num
}

递归

func countNodes(root *TreeNode)int { 
    if root == nil{
        return 0 
    }   
    return countNodes(root.Left) + countNodes(root.Right) + 1
}

小总结

下面总结一下关于计算数量的问题(递归)

一般来说就是在return 后面加1

特别神奇，别问我为什么，反正能用

func countNodes(root *TreeNode)int { 
    if root == nil{
        return 0 
    }   
    return countNodes(root.Left) + countNodes(root.Right) + 1
}

如果推出某个节点的深度

max(high(root.Left),high(root.Right))+1

然后用这第二个总结做个题目

判断平衡二叉树

就是判断左右子树的高度差 <= 1

因此，只要求出左右子树的各个高度就行

height = max(high(root.Left),high(root.Right))+1

自顶向下

// 整体代码
func isBalanced(root *TreeNode) bool {
    if root == nil {
        return true 
    }

    return abs(height(root.Right)-height(root.Left))<=1 && isBalanced(root.Right) && isBalanced(root.Left)
}

func height(root *TreeNode) int {
    if root == nil {
        return 0
    }

    return max(height(root.Left),height(root.Right))+1
}

func max( a , b int ) int {
    if a >b {
        return a 
    }
    return b 
}

func abs(x int)int {
    if x < 0 {
        return -1 * x
    }
    
    return x 
}

由于是自顶向下递归，因此对于同一个节点，函数 height\texttt{height}height 会被重复调用，导致时间复杂度较高

高级版（自底向上）

func isBalanced(root *TreeNode) bool {
    return height(root)>=0 
}

func height(root *TreeNode) int {
    if root == nil {
        return 0
    }

    leftHeight := height(root.Left)
    rightHeight := height(root.Right)

    if leftHeight == -1 || rightHeight == -1 || abs(leftHeight - rightHeight) >1 {
        return -1 
    }

    return max(leftHeight,rightHeight)+1
}

func max( a , b int ) int {
    if a >b {
        return a 
    }
    return b 
}

func abs(x int)int {
    if x < 0 {
        return -1 * x
    }

    return x 
}

很巧妙，多想想

二叉树的最小深度(important)

注意：最小深度是指没有叶子的节点

而不是像最大深度一样，只求最大

所以最小深度的那个节点必定是:

root.left == nil && root.right == nil

func min(a, b int) int {
    if a < b {
        return a;
    }
    return b;
}
// 递归--后序遍历
func minDepth(root *TreeNode) int {
    if root == nil {
        return 0;
    }
    // 左
    if root.Right == nil && root.Left != nil {
        return 1 + minDepth(root.Left);
    }
    // 右
    if root.Left == nil && root.Right != nil {
        return 1 + minDepth(root.Right);
    }
    // 根
    return min(minDepth(root.Left), minDepth(root.Right)) + 1;
}

二叉树的所有路径

这道题目的判定条件是 左右子节点都是nil，但是需要某个值来记录path

递归

func binaryTreePaths(root *TreeNode) []string {
    res := []string{}
    buildPath(root , "" , &res)
    return res 
}

func buildPath (root *TreeNode , path string , res *[]string){
    if root == nil {
        return 
    }

    if root.Left == nil && root.Right == nil{
        path += strconv.Itoa(root.Val)
        *res = append(*res , path)
        return 
    }

    path += strconv.Itoa(root.Val) + "->"
    buildPath(root.Left , path , res)
    buildPath(root.Right, path , res)
}

迭代

很巧妙，她的那个for循环的索引和具体哪个string是可以联系的

func binaryTreePaths(root *TreeNode) []string {
    paths := []string{}
    if root == nil {
        return paths
    }
    nodeQueue := []*TreeNode{}
    pathQueue := []string{}
    nodeQueue = append(nodeQueue, root)
    pathQueue = append(pathQueue, strconv.Itoa(root.Val))

    for i := 0; i < len(nodeQueue); i++ {
        node, path := nodeQueue[i], pathQueue[i]
        if node.Left == nil && node.Right == nil {
            paths = append(paths, path)
            continue
        }
        if node.Left != nil {
            nodeQueue = append(nodeQueue, node.Left)
            pathQueue = append(pathQueue, path + "->" + strconv.Itoa(node.Left.Val))
        }
        if node.Right != nil {
            nodeQueue = append(nodeQueue, node.Right)
            pathQueue = append(pathQueue, path + "->" + strconv.Itoa(node.Right.Val))
        }
    }
    return paths
}

左子叶之和

给定二叉树的根节点 root ，返回所有左叶子之和

1. 确定参数和返回值

因为是求节点，所以只要传入根节点和返回整数就行

2. 确定终止条件，因为是左叶子–空节点或者叶子节点
3. 确定单层递归的逻辑 – 就是需要左子树的左叶子加上右子树的左叶子

递归法

func sumOfLeftLeaves(root *TreeNode) int {
    if root == nil {
        return 0 
    }

    leftValue := sumOfLeftLeaves(root.Left)
    // 需要判断他是左叶子才行
    if root.Left != nil  && root.Left.Left == nil  && root.Left.Right == nil {
        leftValue = root.Left.Val
    }
    rightValue := sumOfLeftLeaves(root.Right)

    return leftValue + rightValue
}

迭代

通过递归的思路写迭代（前序遍历）

func sumOfLeftLeaves(root *TreeNode) int {
    st := make([]*TreeNode,0)
    if root == nil {
        return 0 
    }
    st = append(st,root)
    res := 0 
    for len(st)!= 0 {
        roots := st[len(st)-1]
        st = st[:len(st)-1]
        if roots.Left!=nil && roots.Left.Left == nil && roots.Left.Right == nil {
            res += roots.Left.Val
        }
        if roots.Left!=nil {
            st = append(st , roots.Left)
        }
        if roots.Right!=nil {
            st = append(st , roots.Right)
        }
    }
    return res
}

找树左下角的值

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

递归

使用了全局变量，我觉得开挂了，赢得不体面

var res int 
var depth int 
func findBottomLeftValue(root *TreeNode) int {
    res , depth = 0 , 0 
    dfs (root , 1)
    return res 
}

func dfs (root *TreeNode , dep int){
    if root == nil {
        return 
    }
    if dep>= depth && root.Left == nil && root.Right == nil{
        depth = dep
        res = root.Val
    }
    // 这里必须是右左的顺序，因为要求最左边的叶子
    dfs (root.Right,dep+1)
    dfs (root.Left,dep+1)
}

迭代

前序遍历的递归翻译

func findBottomLeftValue(root *TreeNode)int {
    st := make([]*TreeNode,0)
    if root == nil {
        return -1
    }
    res := root.Val
    st = append(st , root)
    dep := 1 
    depth := 1 
    for len(st)>0 {
        len := len(st)
        for i:= 0 ;i<len;i++{
            node := st[i]
            if dep>= depth && node.Left == nil && node.Right==nil {
                res = node.Val
                depth = dep
            }
            if node.Right !=nil{
                st = append(st,node.Right)
            }
            if node.Left != nil {
                st = append(st,node.Left)
            }
        }
        st = st[len:]
        dep ++ 
    }
    return res 
}

路径总和

路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在根节点到叶子节点的路径，
这条路径上所有节点值相加等于目标和 targetSum 。
如果存在，返回 true ；否则，返回 false 。

递归

// 1. 判断参数和返回值
// 2. 判断限定条件
// 3. 单层的循环条件
func hasPathSum(root *TreeNode, targetSum int) bool {
	if root == nil {
		return false
	}

	targetSum = targetSum - root.Val

	if root.Left == nil && root.Right == nil && targetSum == 0 {
		return true
	}

	return hasPathSum(root.Left, targetSum) || hasPathSum(root.Right, targetSum)
}

迭代

这里不仅是前序遍历，还使用了一点回溯的味道，因为他要记录==nodeSum==，但是如果到了叶子节点发现他们的总和不一样，就需要回溯到上一层的节点，所以就建立一个==slice==去存储某个节点的总和即可

func hasPathSum(root *TreeNode, targetSum int) bool {  
	if root == nil {  
		return false  
	}  
  
	stack := []*TreeNode{root}  
	sumStack := []int{0} // Keep track of the sum at each node  
	for len(stack) > 0 {  
		node := stack[len(stack)-1]  
		stack = stack[:len(stack)-1]  
		nodeSum := sumStack[len(sumStack)-1]  
		sumStack = sumStack[:len(sumStack)-1]  
  
		nodeSum += node.Val  
  
		if node.Left == nil && node.Right == nil {  
			if nodeSum == targetSum {  
				return true  
			}  
		}  
  
		if node.Right != nil {  
			stack = append(stack, node.Right)  
			sumStack = append(sumStack, nodeSum)  
		}  
  
		if node.Left != nil {  
			stack = append(stack, node.Left)  
			sumStack = append(sumStack, nodeSum)  
		}  
	}  
	return false  
}  

从中序与后序遍历序列构造二叉树(important)

简单来说就是 给你一个中序遍历的数组结果和一个后序遍历的数组结果 来构造一棵二叉树

递归

1. 判断参数和返回值

2. 判断限定条件

3. 单层循环逻辑

整道题的关键就是找到左右子树的问题

需要保证： 每次递归传入函数的两个数组一定是某个根下面的左右子树的部分

显而易见的是想要找到左右子树的根可以从后序数组的最后一个元素入手

想要区分左右子树就先从中序数组入手（因为中序遍历是左根右，可以保证==index==左边都是左子树，右边都是右子树）—— 这个中序数组特别重要，因为他是区分左右子树的关键，没有中序数组，只有后序前序是不知道数组的左边右边组成为左右子树

分割后序数组的时候会发现后序数组与中序数组的==index==有关系

最后如果后序数组为空，则表示叶子节点了噢

// 后序数组 + 中序数组
/*
第一步：如果数组大小为零的话，说明是空节点了。
第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。
第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）  切割中序数组相当于就是把中序数组的左右子树分开了
第五步：切割后序数组，切成后序左数组和后序右数组
第六步：递归处理左区间和右区间
*/
func buildTree(inorder []int, postorder []int) *TreeNode {
	if len(postorder) == 0 {
		return nil
	}
	
	node := &TreeNode{
		Val: postorder[len(postorder)-1],
	}

	index := 0
	for i := 0; i < len(inorder); i++ {
		if inorder[i] == node.Val {
			index = i
		}
	}

	node.Left = buildTree(inorder[:index], postorder[:index])
	node.Right = buildTree(inorder[index+1:], postorder[index:len(postorder)-1])

	return node
}

// 中序数组 + 前序数组
// 同样的思维
func buildTree(preorder []int, inorder []int) *TreeNode {
	if len(preorder) == 0 {
		return nil 
	}
	
	node := &TreeNode{
		Val: preorder[0],
	}
	
	index := 0
	for i := 0; i < len(inorder); i++ {
		if inorder[i] == node.Val {
			index = i
		}
	}
	
	node.Left = buildTree(preorder[1:index+1], inorder[:index])
	node.Right = buildTree(preorder[index+1:], inorder[index+1:])
	
	return node 
}

最大二叉树

输入：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 的节点。
    • 空数组，无子节点。

这道题就是左右子树的思路，通过上面一道题的思路来递归求解这道题目，非常简单

递归

package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func constructMaximumBinaryTree(nums []int) *TreeNode {
	if len(nums) == 0 {
		return nil
	}
	maxIndex := 0
	for i := 1; i < len(nums); i++ {
		if nums[i] > nums[maxIndex] {
			maxIndex = i
		}
	}

	node := &TreeNode{
		Val: nums[maxIndex],
	}
	node.Left = constructMaximumBinaryTree(nums[:maxIndex])
	node.Right = constructMaximumBinaryTree(nums[maxIndex+1:])

	return node
}

合并二叉树

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

递归

解题思路和上题和上上题一样

package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
	if root1 == nil {
		return root2
	}
	if root2 == nil {
		return root1
	}
	root1.Val += root2.Val
	root1.Left = mergeTrees(root1.Left, root2.Left)
	root1.Right = mergeTrees(root1.Right, root2.Right)
	return root1
}

迭代

func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
	queue := make([]*TreeNode,0)
	if root1 == nil{
		return root2
	}
	if root2 == nil{
		return root1
	}
	queue = append(queue,root1)
	queue = append(queue,root2)

	for size := len(queue); size>0; size=len(queue) {
		node1 := queue[0]
		queue = queue[1:]
		node2 := queue[0]
		queue = queue[1:]
		node1.Val += node2.Val
		// 左子树都不为空
		if node1.Left != nil && node2.Left != nil {
			queue = append(queue,node1.Left)
			queue = append(queue,node2.Left)
		}
		// 右子树都不为空
		if node1.Right !=nil && node2.Right !=nil {
			queue = append(queue, node1.Right)
			queue = append(queue, node2.Right)
		}
		// 树 1 的左子树为 nil，直接接上树 2 的左子树
		if node1.Left == nil {
			node1.Left = node2.Left
		}
		// 树 1 的右子树为 nil，直接接上树 2 的右子树
		if node1.Right == nil {
			node1.Right = node2.Right
		}
	}
	return root1
}

二叉搜索树

---

一般二叉搜索树会使用==中序遍历==的思想去解决

中序遍历有个很重要的特点– 中序遍历是一个==递增序列==，这个特点和二叉搜索树相符合

二叉搜索树中的搜索

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

过于简单了

func searchBST(root *TreeNode, val int) *TreeNode {
    for root != nil {
        if val == root.Val {
            return root
        }
        if val < root.Val {
            root = root.Left
        } else {
            root = root.Right
        }
    }
    return nil
}

验证二叉搜索树

递归

这边的递归要注意是所有左子树都要小于根节点，这个很重要。

func isValidBST(root *TreeNode) bool {
	return isValidBSTWithRange(root, nil, nil)
}

func isValidBSTWithRange(root *TreeNode, min *int, max *int) bool {
	if root == nil {
		return true
	}
	if min != nil && root.Val <= *min {
		return false
	}
	if max != nil && root.Val >= *max {
		return false
	}
	return isValidBSTWithRange(root.Left, min, &root.Val) && isValidBSTWithRange(root.Right, &root.Val, max)
}

中序遍历

// 这道题的关键是要理解二叉搜索树的性质，即中序遍历的结果是一个递增的序列
// 左 - 根 - 右 的递增形式
func isValidBST1(root *TreeNode) bool {
    stack := make([]*TreeNode, 0)
    inorder := -1 << 63
    for len(stack) > 0 || root != nil {
       // 左
       for root != nil {
          stack = append(stack, root)
          root = root.Left
       }
       // 中
       root = stack[len(stack)-1]
       stack = stack[:len(stack)-1]
       // 因为始终是左根右--左<中<右 所以只要这么判断就行了
       if root.Val <= inorder {
          return false
       }
       inorder = root.Val
       // 右
       root = root.Right
    }
    return true
}

二叉搜索树的最小绝对值

给你一棵二叉搜索树，所有节点，两两之间的最小差值（Val>=0）

递归

func getMiniDiff(root *TreeNode) int {
	ans, pre := math.MaxInt64, -1
	var dfs func(*TreeNode) //这样子可以避免全局变量
	dfs = func(node *TreeNode) {
		if node == nil {
			return
		}
		dfs(node.Left)
		if pre != -1 && node.Val-pre < ans {
			ans = node.Val - pre
		}
		pre = node.Val
		dfs(node.Right)
	}
	dfs(root)
	return ans
}

迭代

func getMinimumDifference(root *TreeNode)int {
	ans , pre := math.MaxInt64 , -1 
	stack := []*TreeNode{}
	for len(stack) > 0 || root != nil {
		for root != nil {
			stack = append(stack,root)
			root = root.Left
		}
		root = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		if pre != -1 && root.Val - pre < ans {
			ans = root.Val - pre
		}
		pre = root.Val
		root = root.Right
	}
	return ans 
}

二叉搜索树中的众数

递归

// 自己做的，不接受反驳
func findMode(root *TreeNode) []int {
	maxNum := make(map[int]int)
	var dfs func(root *TreeNode)
	dfs = func(root *TreeNode) {
		if root == nil {
			return
		}
		dfs(root.Left)
		maxNum[root.Val]++
		dfs(root.Right)
	}
	dfs(root)
	m := 0
	for _, v := range maxNum {
		if v > m {
			m = v
		}
	}
	var res []int
	for k, v := range maxNum {
		if v == m {
			res = append(res, k)
		}
	}
	return res
}

不使用map

func findMode(root *TreeNode) (answer []int) {
    var base, count, maxCount int

    update := func(x int) {
        if x == base {
            count++
        } else {
            base, count = x, 1
        }
        if count == maxCount {
            answer = append(answer, base)
        } else if count > maxCount {
            maxCount = count
            answer = []int{base}
        }
    }

    var dfs func(*TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil {
            return
        }
        dfs(node.Left)
        update(node.Val)
        dfs(node.Right)
    }
    dfs(root)
    return
}

二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

递归

如果要找到公共的祖先，最先想到的肯定是回溯的过程，而和回溯过程相近似的操作就是左右根的操作

下面的代码中查找一定能找到p,q节点，后面的return就是回溯

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	if root == nil {
		return root
	}

	if root == q || root == p {
		return root
	}

	left := lowestCommonAncestor(root.Left, p, q)
	right := lowestCommonAncestor(root.Right, p, q)

	if left != nil && right != nil {
		return root
	}
	if left == nil {
		return right
	}
	return left
}

二叉搜索树的最近公共祖先

记住二叉搜索树是有递增的顺序存在的

因此不如这么想，从根节点出发

如果p,q两个节点的val都比root小,说明root在p,q的左边，这时候==root==就需要变成==root.Left==

如果p,q两个节点的val都比root大,说明root在p,q的右边，这时候==root==就需要变成==root.Right==

这次不如先来理解一下迭代的算法（这个比较好理解）

迭代

func lowestCommonAncestor(root ,p ,q *TreeNode)*TreeNode{
	for root != nil {
		if root.Val>p.Val && root.Val > q.Val{
			root = root.Left
		}else if root.Val<p.Val && root.Val<q.Val{
			root = root.Right
		}else {
			return root 
		}
	}
	return nil 
}

递归

func lowestCommonAncestor(root , p , q *TreeNode)*TreeNode{
    if root.Val>p.Val && root.Val>q.Val{
        return lowestCommonAncestor(root.Left,p,q)
    }else if root.Val<p.Val && root.Val<q.Val{
        return lowestCommonAncestor(root.Right,p,q)
    }else{
        return root 
    }
}

二叉搜索树中的插入操作(difficult)

给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

误区：一开始会想着把这个值放到两个节点之中（很麻烦）

注意： 题目中有描述：可以返回任意有效的结果

所以能不能把val都放到叶子节点中，思考一下比node大的放右边，小的放左边，由此而言，是可以放的，下面就是解题思路：

一直遍历到==node=nil== 表 示 ==node.Left<val<node.Right==

最后判断相应的大小把val放入左或者右即可

递归

func insertIntoBST(root *TreeNode, val int) *TreeNode {
    if root == nil {
        root = &TreeNode{Val: val}
        return root
    }
    if root.Val > val {
        root.Left = insertIntoBST(root.Left, val)
    } else {
        root.Right = insertIntoBST(root.Right, val)
    }
    return root
}

迭代

func insertIntoBST(root *TreeNode, val int) *TreeNode {
    if root == nil {
        return &TreeNode{Val: val}
    }
    p := root
    for p != nil {
        if val < p.Val {
            if p.Left == nil {
                p.Left = &TreeNode{Val: val}
                break
            }
            p = p.Left
        } else {
            if p.Right == nil {
                p.Right = &TreeNode{Val: val}
                break
            }
            p = p.Right
        }
    }
    return root
}

删除二叉搜索树的节点(difficult)

参照上面一题的思路，删除某个一个节点，那么这个原本节点的树应该挪到哪里去，这是个问题。

正常人—–我一开始反应是直接把后面的节点接上去

但是后来我发现，不如直接把这棵树塞到叶子节点下面

由于二叉搜索树的性质，左子树永远比右子树要小，那么根节点的去除时，是不是可以把左子树放到右子树的左子树叶子下面，然后把整棵右子树接上去呢，这样子也不用考虑其他的情况了，具体代码就是下面：

感谢代码随想录

迭代

func deleteNode(root *TreeNode, key int) *TreeNode {
	if root == nil {
		return root
	}
	cur := root
	var pre *TreeNode
	for cur != nil {
		if cur.Val == key {
			break
		}
		pre = cur
		if cur.Val > key {
			cur = cur.Left
		} else {
			cur = cur.Right
		}
	}
	if pre == nil {
		return deleteOneNode(cur)
	}
	if pre.Left != nil && pre.Left.Val == key {
		pre.Left = deleteOneNode(cur)
	}
	if pre.Right != nil && pre.Right.Val == key {
		pre.Right = deleteOneNode(cur)
	}
	return root
}

func deleteOneNode(root *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	if root.Right == nil {
		return root.Left
	}
	cur := root.Right
	for cur.Left != nil {
		cur = cur.Left
	}
	cur.Left = root.Left
	return root.Right
}

递归

func deleteNode(root *TreeNode, key int) *TreeNode {
    if root == nil {
        return nil
    }
    if key < root.Val {
        root.Left = deleteNode(root.Left, key)
        return root
    }
    if key > root.Val {
        root.Right = deleteNode(root.Right, key)
        return root
    }
    if root.Right == nil {
        return root.Left
    }
    if root.Left == nil{
        return root.Right
    }
    minnode := root.Right
    for minnode.Left != nil {
        minnode = minnode.Left
    }
    root.Val = minnode.Val
    root.Right = deleteNode1(root.Right)
    return root
}

func deleteNode1(root *TreeNode)*TreeNode {
    if root.Left == nil {
        pRight := root.Right
        root.Right = nil
        return pRight
    }
    root.Left = deleteNode1(root.Left)
    return root
}

修剪二叉搜索树

给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。

有点麻烦，展示就写递归这个版本

具体操作还是有点蒙蔽

递归

func trimBST(root *TreeNode, low int, high int) *TreeNode {
	if root == nil {
		return nil
	}
	// 直接把不符合的节点跳过，虽然会进入递归，但是不计入结果（即不会使用node.Left=去计入节点）
	if root.Val < low {
		return trimBST(root.Right, low, high)
	}
	if root.Val > high {
		return trimBST(root.Left, low, high)
	}
	// 这里是通过return来实现二次重塑树的
	root.Left = trimBST(root.Left, low, high)
	root.Right = trimBST(root.Right, low, high)
	return root
}

将有序数组转化为平衡二叉搜索树

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

这道题目跟之前 用中序和后序遍历构造二叉树的题目很像

递归

func sortedArrayToBST(nums []int) *TreeNode {
	return helper(nums, 0, len(nums)-1)
}

func helper(nums []int, left, right int) *TreeNode {
	if left > right {
		return nil
	}

	mid := left + (right-left)/2
	root := &TreeNode{Val: nums[mid]}
	root.Left = helper(nums, left, mid-1)
	root.Right = helper(nums, mid+1, right)
	return root
}

递归精简

func sortedArrayToBST(nums []int)*TreeNode{
	if len(nums)==0 {
		return nil
	}
	mid:=len(nums)/2
	root:=&TreeNode{Val:nums[mid]}
	
	root.Left=sortedArrayToBST(nums[:mid])
	root.Right=sortedArrayToBST(nums[mid+1:])
	return root
}

把二叉搜索树转化为累加树

这个累加树是怎么一回事呢：具体来说就是右根左，然后依次相加

递归

只能说所谓的函数变量特别好用，跟之前做的某道题目特别像，具体哪道题我忘记了

func convertBST(root *TreeNode) *TreeNode {
	sum := 0 
	var dfs func(*TreeNode)
	dfs = func(node *TreeNode) {
		if node == nil {
			return
		}
		dfs(node.Right)
        sum += node.Val
        node.Val = sum 
		dfs(node.Left)
	}
	dfs(root)
	return root
}

总结

普天同庆，感觉对递归的感觉熟悉了一点

• 前中后遍历 使用stack
• 层状遍历
• 全局变量
• 二叉搜索树永远的左根右
• 永远存在的回溯的味道

🆗，就此进入下一章==回溯==，拜拜咯