前序遍历：先访问根节点，再前序遍历左子树，再前序遍历右子树 中序遍历：先中序遍历左子树，再访问根节点，再中序遍历右子树 后序遍历：先后序遍历左子树，再后序遍历右子树，再访问根节点
注意点
- 以根访问顺序决定是什么遍历
- 左子树都是优先右子树
funcpreorderTraversal(root*TreeNode) {
ifroot==nil{
return
}
// 先访问根再访问左右fmt.Println(root.Val)
preorderTraversal(root.Left)
preorderTraversal(root.Right)
}// V3：通过非递归遍历funcpreorderTraversal(root*TreeNode) []int {
// 非递归ifroot==nil{
returnnil
}
result:=make([]int,0)
stack:=make([]*TreeNode,0)
forroot!=nil||len(stack)!=0{
forroot!=nil{
// 前序遍历，所以先保存结果result=append(result,root.Val)
stack=append(stack,root)
root=root.Left
}
// popnode:=stack[len(stack)-1]
stack=stack[:len(stack)-1]
root=node.Right
}
returnresult
}// 思路：通过stack 保存已经访问的元素，用于原路返回funcinorderTraversal(root*TreeNode) []int {
result:=make([]int, 0)
ifroot==nil {
returnresult
}
stack:=make([]*TreeNode, 0)
forlen(stack) >0||root!=nil {
forroot!=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
}
returnresult
}funcpostorderTraversal(root*TreeNode) []int {
// 通过lastVisit标识右子节点是否已经弹出ifroot==nil {
returnnil
}
result:=make([]int, 0)
stack:=make([]*TreeNode, 0)
varlastVisit*TreeNodeforroot!=nil||len(stack) !=0 {
forroot!=nil {
stack=append(stack, root)
root=root.Left
}
// 这里先看看，先不弹出node:=stack[len(stack)-1]
// 根节点必须在右节点弹出之后，再弹出ifnode.Right==nil||node.Right==lastVisit {
stack=stack[:len(stack)-1] // popresult=append(result, node.Val)
// 标记当前这个节点已经弹出过lastVisit=node
} else {
root=node.Right
}
}
returnresult
}注意点
- 核心就是：根节点必须在右节点弹出之后，再弹出
typeTreeNodestruct {
ValintLeft*TreeNodeRight*TreeNode
}
funcpreorderTraversal(root*TreeNode) []int {
result:=make([]int, 0)
dfs(root, &result)
returnresult
}
// V1：深度遍历，结果指针作为参数传入到函数内部funcdfs(root*TreeNode, result*[]int) {
ifroot==nil {
return
}
*result=append(*result, root.Val)
dfs(root.Left, result)
dfs(root.Right, result)
}// V2：通过分治法遍历funcpreorderTraversal(root*TreeNode) []int {
result:=divideAndConquer(root)
returnresult
}
funcdivideAndConquer(root*TreeNode) []int {
result:=make([]int, 0)
// 返回条件(null & leaf)ifroot==nil {
returnresult
}
// 分治(Divide)left:=divideAndConquer(root.Left)
right:=divideAndConquer(root.Right)
// 合并结果(Conquer)result=append(result, root.Val)
result=append(result, left...)
result=append(result, right...)
returnresult
}注意点：
DFS 深度搜索（从上到下） 和分治法区别：前者一般将最终结果通过指针参数传入，后者一般递归返回结果最后合并
funclevelOrder(root*TreeNode) [][]int {
// 通过上一层的长度确定下一层的元素result:=make([][]int, 0)
ifroot==nil {
returnresult
}
queue:=make([]*TreeNode, 0)
queue=append(queue, root)
forlen(queue) >0 {
list:=make([]int, 0)
// 为什么要取length？// 记录当前层有多少元素（遍历当前层，再添加下一层）l:=len(queue)
fori:=0; i<l; i++ {
// 出队列level:=queue[0]
queue=queue[1:]
list=append(list, level.Val)
iflevel.Left!=nil {
queue=append(queue, level.Left)
}
iflevel.Right!=nil {
queue=append(queue, level.Right)
}
}
result=append(result, list)
}
returnresult
}先分别处理局部，再合并结果
适用场景
- 快速排序
- 归并排序
- 二叉树相关问题
分治法模板
- 递归返回条件
- 分段处理
- 合并结果
functraversal(root*TreeNode) ResultType {
// nil or leafifroot==nil {
// do something and return
}
// DivideResultTypeleft=traversal(root.Left)
ResultTyperight=traversal(root.Right)
// ConquerResultTyperesult=Mergefromleftandrightreturnresult
}// V2：通过分治法遍历二叉树funcpreorderTraversal(root*TreeNode) []int {
result:=divideAndConquer(root)
returnresult
}
funcdivideAndConquer(root*TreeNode) []int {
result:=make([]int, 0)
// 返回条件(null & leaf)ifroot==nil {
returnresult
}
// 分治(Divide)left:=divideAndConquer(root.Left)
right:=divideAndConquer(root.Right)
// 合并结果(Conquer)result=append(result, root.Val)
result=append(result, left...)
result=append(result, right...)
returnresult
}funcMergeSort(nums []int) []int {
returnmergeSort(nums)
}
funcmergeSort(nums []int) []int {
iflen(nums) <=1 {
returnnums
}
// 分治法：divide 分为两段mid:=len(nums) /2left:=mergeSort(nums[:mid])
right:=mergeSort(nums[mid:])
// 合并两段数据result:=merge(left, right)
returnresult
}
funcmerge(left, right []int) (result []int) {
// 两边数组合并游标l:=0r:=0// 注意不能越界forl<len(left) &&r<len(right) {
// 谁小合并谁ifleft[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
}注意点
递归需要返回结果用于合并
funcQuickSort(nums []int) []int {
// 思路：把一个数组分为左右两段，左段小于右段，类似分治法没有合并过程quickSort(nums, 0, len(nums)-1)
returnnums
}
// 原地交换，所以传入交换索引funcquickSort(nums []int, start, endint) {
ifstart<end {
// 分治法：dividepivot:=partition(nums, start, end)
quickSort(nums, 0, pivot-1)
quickSort(nums, pivot+1, end)
}
}
// 分区funcpartition(nums []int, start, endint) int {
p:=nums[end]
i:=startforj:=start; j<end; j++ {
ifnums[j] <p {
swap(nums, i, j)
i++
}
}
// 把中间的值换为用于比较的基准值swap(nums, i, end)
returni
}
funcswap(nums []int, i, jint) {
t:=nums[i]
nums[i] =nums[j]
nums[j] =t
}注意点：
快排由于是原地交换所以没有合并过程 传入的索引是存在的索引（如：0、length-1 等），越界可能导致崩溃
常见题目示例
给定一个二叉树，找出其最大深度。
思路：分治法
funcmaxDepth(root*TreeNode) int {
// 返回条件处理ifroot==nil {
return0
}
// divide：分左右子树分别计算left:=maxDepth(root.Left)
right:=maxDepth(root.Right)
// conquer：合并左右子树结果ifleft>right {
returnleft+1
}
returnright+1
}给定一个二叉树，判断它是否是高度平衡的二叉树。
思路：分治法，左边平衡 && 右边平衡 && 左右两边高度 <= 1， 因为需要返回是否平衡及高度，要么返回两个数据，要么合并两个数据， 所以用-1 表示不平衡，>0 表示树高度（二义性：一个变量有两种含义）。
funcisBalanced(root*TreeNode) bool {
ifmaxDepth(root) ==-1 {
returnfalse
}
returntrue
}
funcmaxDepth(root*TreeNode) int {
// checkifroot==nil {
return0
}
left:=maxDepth(root.Left)
right:=maxDepth(root.Right)
// 为什么返回-1呢？（变量具有二义性）ifleft==-1||right==-1||left-right>1||right-left>1 {
return-1
}
ifleft>right {
returnleft+1
}
returnright+1
}注意
一般工程中，结果通过两个变量来返回，不建议用一个变量表示两种含义
给定一个非空二叉树，返回其最大路径和。
思路：分治法，分为三种情况：左子树最大路径和最大，右子树最大路径和最大，左右子树最大加根节点最大，需要保存两个变量：一个保存子树最大路径和，一个保存左右加根节点和，然后比较这个两个变量选择最大值即可
typeResultTypestruct {
SinglePathint// 保存单边最大值MaxPathint// 保存最大值（单边或者两个单边+根的值）
}
funcmaxPathSum(root*TreeNode) int {
result:=helper(root)
returnresult.MaxPath
}
funchelper(root*TreeNode) ResultType {
// checkifroot==nil {
returnResultType{
SinglePath: 0,
MaxPath: -(1<<31),
}
}
// Divideleft:=helper(root.Left)
right:=helper(root.Right)
// Conquerresult:=ResultType{}
// 求单边最大值ifleft.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)
returnresult
}
funcmax(a,bint) int {
ifa>b {
returna
}
returnb
}lowest-common-ancestor-of-a-binary-tree
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
思路：分治法，有左子树的公共祖先或者有右子树的公共祖先，就返回子树的祖先，否则返回根节点
funclowestCommonAncestor(root, p, q*TreeNode) *TreeNode {
// checkifroot==nil {
returnroot
}
// 相等 直接返回root节点即可ifroot==p||root==q {
returnroot
}
// Divideleft:=lowestCommonAncestor(root.Left, p, q)
right:=lowestCommonAncestor(root.Right, p, q)
// Conquer// 左右两边都不为空，则根节点为祖先ifleft!=nil&&right!=nil {
returnroot
}
ifleft!=nil {
returnleft
}
ifright!=nil {
returnright
}
returnnil
}binary-tree-level-order-traversal
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）
思路：用一个队列记录一层的元素，然后扫描这一层元素添加下一层元素到队列（一个数进去出来一次，所以复杂度 O(logN)）
funclevelOrder(root*TreeNode) [][]int {
result:=make([][]int, 0)
ifroot==nil {
returnresult
}
queue:=make([]*TreeNode, 0)
queue=append(queue, root)
forlen(queue) >0 {
list:=make([]int, 0)
// 为什么要取length？// 记录当前层有多少元素（遍历当前层，再添加下一层）l:=len(queue)
fori:=0; i<l; i++ {
// 出队列level:=queue[0]
queue=queue[1:]
list=append(list, level.Val)
iflevel.Left!=nil {
queue=append(queue, level.Left)
}
iflevel.Right!=nil {
queue=append(queue, level.Right)
}
}
result=append(result, list)
}
returnresult
}binary-tree-level-order-traversal-ii
给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
思路：在层级遍历的基础上，翻转一下结果即可
funclevelOrderBottom(root*TreeNode) [][]int {
result:=levelOrder(root)
// 翻转结果reverse(result)
returnresult
}
funcreverse(nums [][]int) {
fori, j:=0, len(nums)-1; i<j; i, j=i+1, j-1 {
nums[i], nums[j] =nums[j], nums[i]
}
}
funclevelOrder(root*TreeNode) [][]int {
result:=make([][]int, 0)
ifroot==nil {
returnresult
}
queue:=make([]*TreeNode, 0)
queue=append(queue, root)
forlen(queue) >0 {
list:=make([]int, 0)
// 为什么要取length？// 记录当前层有多少元素（遍历当前层，再添加下一层）l:=len(queue)
fori:=0; i<l; i++ {
// 出队列level:=queue[0]
queue=queue[1:]
list=append(list, level.Val)
iflevel.Left!=nil {
queue=append(queue, level.Left)
}
iflevel.Right!=nil {
queue=append(queue, level.Right)
}
}
result=append(result, list)
}
returnresult
}binary-tree-zigzag-level-order-traversal
给定一个二叉树，返回其节点值的锯齿形层次遍历。Z 字形遍历
funczigzagLevelOrder(root*TreeNode) [][]int {
result:=make([][]int, 0)
ifroot==nil {
returnresult
}
queue:=make([]*TreeNode, 0)
queue=append(queue, root)
toggle:=falseforlen(queue) >0 {
list:=make([]int, 0)
// 记录当前层有多少元素（遍历当前层，再添加下一层）l:=len(queue)
fori:=0; i<l; i++ {
// 出队列level:=queue[0]
queue=queue[1:]
list=append(list, level.Val)
iflevel.Left!=nil {
queue=append(queue, level.Left)
}
iflevel.Right!=nil {
queue=append(queue, level.Right)
}
}
iftoggle {
reverse(list)
}
result=append(result, list)
toggle=!toggle
}
returnresult
}
funcreverse(nums []int) {
fori:=0; i<len(nums)/2; i++ {
nums[i], nums[len(nums)-1-i] =nums[len(nums)-1-i], nums[i]
}
}给定一个二叉树，判断其是否是一个有效的二叉搜索树。
思路 1：中序遍历，检查结果列表是否已经有序
思路 2：分治法，判断左 MAX < 根 < 右 MIN
// v1funcisValidBST(root*TreeNode) bool {
result:=make([]int, 0)
inOrder(root, &result)
// check orderfori:=0; i<len(result) -1; i++{
ifresult[i] >=result[i+1] {
returnfalse
}
}
returntrue
}
funcinOrder(root*TreeNode, result*[]int) {
ifroot==nil{
return
}
inOrder(root.Left, result)
*result=append(*result, root.Val)
inOrder(root.Right, result)
}
// v2分治法typeResultTypestruct {
IsValidbool// 记录左右两边最大最小值，和根节点进行比较Max*TreeNodeMin*TreeNode
}
funcisValidBST2(root*TreeNode) bool {
result:=helper(root)
returnresult.IsValid
}
funchelper(root*TreeNode) ResultType {
result:=ResultType{}
// checkifroot==nil {
result.IsValid=truereturnresult
}
left:=helper(root.Left)
right:=helper(root.Right)
if!left.IsValid||!right.IsValid {
result.IsValid=falsereturnresult
}
ifleft.Max!=nil&&left.Max.Val>=root.Val {
result.IsValid=falsereturnresult
}
ifright.Min!=nil&&right.Min.Val<=root.Val {
result.IsValid=falsereturnresult
}
result.IsValid=true// 如果左边还有更小的3，就用更小的节点，不用4// 5// / \// 1 4// / \// 3 6result.Min=rootifleft.Min!=nil {
result.Min=left.Min
}
result.Max=rootifright.Max!=nil {
result.Max=right.Max
}
returnresult
}insert-into-a-binary-search-tree
给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。
思路：找到最后一个叶子节点满足插入条件即可
// DFS查找插入位置funcinsertIntoBST(root*TreeNode, valint) *TreeNode {
ifroot==nil {
root=&TreeNode{Val: val}
returnroot
}
ifroot.Val>val {
root.Left=insertIntoBST(root.Left, val)
} else {
root.Right=insertIntoBST(root.Right, val)
}
returnroot
}- 掌握二叉树递归与非递归遍历
- 理解 DFS 前序遍历与分治法
- 理解 BFS 层次遍历