二叉树
知识点
二叉树遍历
前序遍历:先访问根节点,再前序遍历左子树,再前序遍历右子树 中序遍历:先中序遍历左子树,再访问根节点,再中序遍历右子树 后序遍历:先后序遍历左子树,再后序遍历右子树,再访问根节点
注意点
- 以根访问顺序决定是什么遍历
- 左子树都是优先右子树
前序递归
func preorderTraversal(root *TreeNode) {
if root==nil{
return
}
// 先访问根再访问左右
fmt.Println(root.Val)
preorderTraversal(root.Left)
preorderTraversal(root.Right)
}
前序非递归
// V3:通过非递归遍历
func preorderTraversal(root *TreeNode) []int {
// 非递归
if root == nil{
return nil
}
result:=make([]int,0)
stack:=make([]*TreeNode,0)
for root!=nil || len(stack)!=0{
for root !=nil{
// 前序遍历,所以先保存结果
result=append(result,root.Val)
stack=append(stack,root)
root=root.Left
}
// pop
node:=stack[len(stack)-1]
stack=stack[:len(stack)-1]
root=node.Right
}
return result
}
中序非递归
// 思路:通过stack 保存已经访问的元素,用于原路返回
func inorderTraversal(root *TreeNode) []int {
result := make([]int, 0)
if root == nil {
return result
}
stack := make([]*TreeNode, 0)
for len(stack) > 0 || root != nil {
for root != nil {
stack = append(stack, root)
root = root.Left // 一直向左
}
// 弹出
val := stack[len(stack)-1]
stack = stack[:len(stack)-1]
result = append(result, val.Val)
root = val.Right
}
return result
}
后序非递归
func postorderTraversal(root *TreeNode) []int {
// 通过lastVisit标识右子节点是否已经弹出
if root == nil {
return nil
}
result := make([]int, 0)
stack := make([]*TreeNode, 0)
var lastVisit *TreeNode
for root != nil || len(stack) != 0 {
for root != nil {
stack = append(stack, root)
root = root.Left
}
// 这里先看看,先不弹出
node:= stack[len(stack)-1]
// 根节点必须在右节点弹出之后,再弹出
if node.Right == nil || node.Right == lastVisit {
stack = stack[:len(stack)-1] // pop
result = append(result, node.Val)
// 标记当前这个节点已经弹出过
lastVisit = node
} else {
root = node.Right
}
}
return result
}
注意点
- 核心就是:根节点必须在右节点弹出之后,再弹出
DFS 深度搜索-从上到下
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func preorderTraversal(root *TreeNode) []int {
result := make([]int, 0)
dfs(root, &result)
return result
}
// V1:深度遍历,结果指针作为参数传入到函数内部
func dfs(root *TreeNode, result *[]int) {
if root == nil {
return
}
*result = append(*result, root.Val)
dfs(root.Left, result)
dfs(root.Right, result)
}
DFS 深度搜索-从下向上(分治法)
// V2:通过分治法遍历
func preorderTraversal(root *TreeNode) []int {
result := divideAndConquer(root)
return result
}
func divideAndConquer(root *TreeNode) []int {
result := make([]int, 0)
// 返回条件(null & leaf)
if root == nil {
return result
}
// 分治(Divide)
left := divideAndConquer(root.Left)
right := divideAndConquer(root.Right)
// 合并结果(Conquer)
result = append(result, root.Val)
result = append(result, left...)
result = append(result, right...)
return result
}
注意点:
DFS 深度搜索(从上到下) 和分治法区别:前者一般将最终结果通过指针参数传入,后者一般递归返回结果最后合并
BFS 层次遍历
func levelOrder(root *TreeNode) [][]int {
// 通过上一层的长度确定下一层的元素
result := make([][]int, 0)
if root == nil {
return result
}
queue := make([]*TreeNode, 0)
queue = append(queue, root)
for len(queue) > 0 {
list := make([]int, 0)
// 为什么要取length?
// 记录当前层有多少元素(遍历当前层,再添加下一层)
l := len(queue)
for i := 0; i < l; i++ {
// 出队列
level := queue[0]
queue = queue[1:]
list = append(list, level.Val)
if level.Left != nil {
queue = append(queue, level.Left)
}
if level.Right != nil {
queue = append(queue, level.Right)
}
}
result = append(result, list)
}
return result
}
分治法应用
先分别处理局部,再合并结果
适用场景
- 快速排序
- 归并排序
- 二叉树相关问题
分治法模板
- 递归返回条件
- 分段处理
- 合并结果
func traversal(root *TreeNode) ResultType {
// nil or leaf
if root == nil {
// do something and return
}
// Divide
ResultType left = traversal(root.Left)
ResultType right = traversal(root.Right)
// Conquer
ResultType result = Merge from left and right
return result
}
典型示例
// V2:通过分治法遍历二叉树
func preorderTraversal(root *TreeNode) []int {
result := divideAndConquer(root)
return result
}
func divideAndConquer(root *TreeNode) []int {
result := make([]int, 0)
// 返回条件(null & leaf)
if root == nil {
return result
}
// 分治(Divide)
left := divideAndConquer(root.Left)
right := divideAndConquer(root.Right)
// 合并结果(Conquer)
result = append(result, root.Val)
result = append(result, left...)
result = append(result, right...)
return result
}
归并排序
func MergeSort(nums []int) []int {
return mergeSort(nums)
}
func mergeSort(nums []int) []int {
if len(nums) <= 1 {
return nums
}
// 分治法:divide 分为两段
mid := len(nums) / 2
left := mergeSort(nums[:mid])
right := mergeSort(nums[mid:])
// 合并两段数据
result := merge(left, right)
return result
}
func merge(left, right []int) (result []int) {
// 两边数组合并游标
l := 0
r := 0
// 注意不能越界
for l < len(left) && r < len(right) {
// 谁小合并谁
if left[l] > right[r] {
result = append(result, right[r])
r++
} else {
result = append(result, left[l])
l++
}
}
// 剩余部分合并
result = append(result, left[l:]...)
result = append(result, right[r:]...)
return
}
注意点
递归需要返回结果用于合并
快速排序
func QuickSort(nums []int) []int {
// 思路:把一个数组分为左右两段,左段小于右段,类似分治法没有合并过程
quickSort(nums, 0, len(nums)-1)
return nums
}
// 原地交换,所以传入交换索引
func quickSort(nums []int, start, end int) {
if start < end {
// 分治法:divide
pivot := partition(nums, start, end)
quickSort(nums, 0, pivot-1)
quickSort(nums, pivot+1, end)
}
}
// 分区
func partition(nums []int, start, end int) int {
p := nums[end]
i := start
for j := start; j < end; j++ {
if nums[j] < p {
swap(nums, i, j)
i++
}
}
// 把中间的值换为用于比较的基准值
swap(nums, i, end)
return i
}
func swap(nums []int, i, j int) {
t := nums[i]
nums[i] = nums[j]
nums[j] = t
}
注意点:
快排由于是原地交换所以没有合并过程 传入的索引是存在的索引(如:0、length-1 等),越界可能导致崩溃
常见题目示例
maximum-depth-of-binary-tree
给定一个二叉树,找出其最大深度。
思路:分治法
func maxDepth(root *TreeNode) int {
// 返回条件处理
if root == nil {
return 0
}
// divide:分左右子树分别计算
left := maxDepth(root.Left)
right := maxDepth(root.Right)
// conquer:合并左右子树结果
if left > right {
return left + 1
}
return right + 1
}
balanced-binary-tree
给定一个二叉树,判断它是否是高度平衡的二叉树。
思路:分治法,左边平衡 && 右边平衡 && 左右两边高度 <= 1, 因为需要返回是否平衡及高度,要么返回两个数据,要么合并两个数据, 所以用-1 表示不平衡,>0 表示树高度(二义性:一个变量有两种含义)。
func isBalanced(root *TreeNode) bool {
if maxDepth(root) == -1 {
return false
}
return true
}
func maxDepth(root *TreeNode) int {
// check
if root == nil {
return 0
}
left := maxDepth(root.Left)
right := maxDepth(root.Right)
// 为什么返回-1呢?(变量具有二义性)
if left == -1 || right == -1 || left-right > 1 || right-left > 1 {
return -1
}
if left > right {
return left + 1
}
return right + 1
}
注意
一般工程中,结果通过两个变量来返回,不建议用一个变量表示两种含义
binary-tree-maximum-path-sum
给定一个非空二叉树,返回其最大路径和。
思路:分治法,分为三种情况:左子树最大路径和最大,右子树最大路径和最大,左右子树最大加根节点最大,需要保存两个变量:一个保存子树最大路径和,一个保存左右加根节点和,然后比较这个两个变量选择最大值即可
type ResultType struct {
SinglePath int // 保存单边最大值
MaxPath int // 保存最大值(单边或者两个单边+根的值)
}
func maxPathSum(root *TreeNode) int {
result := helper(root)
return result.MaxPath
}
func helper(root *TreeNode) ResultType {
// check
if root == nil {
return ResultType{
SinglePath: 0,
MaxPath: -(1 << 31),
}
}
// Divide
left := helper(root.Left)
right := helper(root.Right)
// Conquer
result := ResultType{}
// 求单边最大值
if left.SinglePath > right.SinglePath {
result.SinglePath = max(left.SinglePath + root.Val, 0)
} else {
result.SinglePath = max(right.SinglePath + root.Val, 0)
}
// 求两边加根最大值
maxPath := max(right.MaxPath, left.MaxPath)
result.MaxPath = max(maxPath,left.SinglePath+right.SinglePath+root.Val)
return result
}
func max(a,b int) int {
if a > b {
return a
}
return b
}
lowest-common-ancestor-of-a-binary-tree
lowest-common-ancestor-of-a-binary-tree
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
思路:分治法,有左子树的公共祖先或者有右子树的公共祖先,就返回子树的祖先,否则返回根节点
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
// check
if root == nil {
return root
}
// 相等 直接返回root节点即可
if root == p || root == q {
return root
}
// Divide
left := lowestCommonAncestor(root.Left, p, q)
right := lowestCommonAncestor(root.Right, p, q)
// Conquer
// 左右两边都不为空,则根节点为祖先
if left != nil && right != nil {
return root
}
if left != nil {
return left
}
if right != nil {
return right
}
return nil
}
BFS 层次应用
binary-tree-level-order-traversal
binary-tree-level-order-traversal
给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)
思路:用一个队列记录一层的元素,然后扫描这一层元素添加下一层元素到队列(一个数进去出来一次,所以复杂度 O(logN))
func levelOrder(root *TreeNode) [][]int {
result := make([][]int, 0)
if root == nil {
return result
}
queue := make([]*TreeNode, 0)
queue = append(queue, root)
for len(queue) > 0 {
list := make([]int, 0)
// 为什么要取length?
// 记录当前层有多少元素(遍历当前层,再添加下一层)
l := len(queue)
for i := 0; i < l; i++ {
// 出队列
level := queue[0]
queue = queue[1:]
list = append(list, level.Val)
if level.Left != nil {
queue = append(queue, level.Left)
}
if level.Right != nil {
queue = append(queue, level.Right)
}
}
result = append(result, list)
}
return result
}
binary-tree-level-order-traversal-ii
binary-tree-level-order-traversal-ii
给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
思路:在层级遍历的基础上,翻转一下结果即可
func levelOrderBottom(root *TreeNode) [][]int {
result := levelOrder(root)
// 翻转结果
reverse(result)
return result
}
func reverse(nums [][]int) {
for i, j := 0, len(nums)-1; i < j; i, j = i+1, j-1 {
nums[i], nums[j] = nums[j], nums[i]
}
}
func levelOrder(root *TreeNode) [][]int {
result := make([][]int, 0)
if root == nil {
return result
}
queue := make([]*TreeNode, 0)
queue = append(queue, root)
for len(queue) > 0 {
list := make([]int, 0)
// 为什么要取length?
// 记录当前层有多少元素(遍历当前层,再添加下一层)
l := len(queue)
for i := 0; i < l; i++ {
// 出队列
level := queue[0]
queue = queue[1:]
list = append(list, level.Val)
if level.Left != nil {
queue = append(queue, level.Left)
}
if level.Right != nil {
queue = append(queue, level.Right)
}
}
result = append(result, list)
}
return result
}
binary-tree-zigzag-level-order-traversal
binary-tree-zigzag-level-order-traversal
给定一个二叉树,返回其节点值的锯齿形层次遍历。Z 字形遍历
func zigzagLevelOrder(root *TreeNode) [][]int {
result := make([][]int, 0)
if root == nil {
return result
}
queue := make([]*TreeNode, 0)
queue = append(queue, root)
toggle := false
for len(queue) > 0 {
list := make([]int, 0)
// 记录当前层有多少元素(遍历当前层,再添加下一层)
l := len(queue)
for i := 0; i < l; i++ {
// 出队列
level := queue[0]
queue = queue[1:]
list = append(list, level.Val)
if level.Left != nil {
queue = append(queue, level.Left)
}
if level.Right != nil {
queue = append(queue, level.Right)
}
}
if toggle {
reverse(list)
}
result = append(result, list)
toggle = !toggle
}
return result
}
func reverse(nums []int) {
for i := 0; i < len(nums)/2; i++ {
nums[i], nums[len(nums)-1-i] = nums[len(nums)-1-i], nums[i]
}
}
二叉搜索树应用
validate-binary-search-tree
给定一个二叉树,判断其是否是一个有效的二叉搜索树。
思路 1:中序遍历,检查结果列表是否已经有序
思路 2:分治法,判断左 MAX < 根 < 右 MIN
// v1
func isValidBST(root *TreeNode) bool {
result := make([]int, 0)
inOrder(root, &result)
// check order
for i := 0; i < len(result) - 1; i++{
if result[i] >= result[i+1] {
return false
}
}
return true
}
func inOrder(root *TreeNode, result *[]int) {
if root == nil{
return
}
inOrder(root.Left, result)
*result = append(*result, root.Val)
inOrder(root.Right, result)
}
// v2分治法
type ResultType struct {
IsValid bool
// 记录左右两边最大最小值,和根节点进行比较
Max *TreeNode
Min *TreeNode
}
func isValidBST2(root *TreeNode) bool {
result := helper(root)
return result.IsValid
}
func helper(root *TreeNode) ResultType {
result := ResultType{}
// check
if root == nil {
result.IsValid = true
return result
}
left := helper(root.Left)
right := helper(root.Right)
if !left.IsValid || !right.IsValid {
result.IsValid = false
return result
}
if left.Max != nil && left.Max.Val >= root.Val {
result.IsValid = false
return result
}
if right.Min != nil && right.Min.Val <= root.Val {
result.IsValid = false
return result
}
result.IsValid = true
// 如果左边还有更小的3,就用更小的节点,不用4
// 5
// / \
// 1 4
// / \
// 3 6
result.Min = root
if left.Min != nil {
result.Min = left.Min
}
result.Max = root
if right.Max != nil {
result.Max = right.Max
}
return result
}
insert-into-a-binary-search-tree
insert-into-a-binary-search-tree
给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。
思路:找到最后一个叶子节点满足插入条件即可
// DFS查找插入位置
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
}
总结
- 掌握二叉树递归与非递归遍历
- 理解 DFS 前序遍历与分治法
- 理解 BFS 层次遍历
练习
- [ ] maximum-depth-of-binary-tree
- [ ] balanced-binary-tree
- [ ] binary-tree-maximum-path-sum
- [ ] lowest-common-ancestor-of-a-binary-tree
- [ ] binary-tree-level-order-traversal
- [ ] binary-tree-level-order-traversal-ii
- [ ] binary-tree-zigzag-level-order-traversal
- [ ] validate-binary-search-tree
- [ ] insert-into-a-binary-search-tree