关于树的算法本人认为主要就是记住树的各种遍历中序遍历先序遍历后序遍历和层序遍历本质上也就是要求你掌握深度优先搜索和广度优先搜索。树的深度优先搜索可以用递归和栈两种方法来实现递归本质就是压栈出栈的过程层序遍历广度优先搜索一般用队列实现。其实一般到图论我们才讲深度优先搜索和广度优先搜索但树也是图的一种嘛博主就这样说了注意写树的题目不要太在意递归的细节这样可能会把自己绕进去。当你掌握了以上两种算法相信树的大部分算法你就都能解决了。1.树的遍历方式1.1二叉树的层序遍历这个代码没什么讲得就是用队列存储当前层的代码然后在遍历当前层的结点的同时加入下一层结点把当前层的结点全部压入ans就行了看不懂的同学就自己拿草稿纸一步步推算吧大家都是这么过来的func levelOrder(root *TreeNode) [][]int { if rootnil{ return [][]int{} } var ans [][]int var queue []*TreeNode queueappend(queue,root) for len(queue)0{ size:len(queue)//记录当前层节点的个数 var res []int//存储当前层的结点的值 for i:0;isize;i{ curNode:queue[0] queuequeue[1:] resappend(res,curNode.Val) //下一层节点压入队列 if curNode.Left!nil{ queueappend(queue,curNode.Left) } if curNode.Right!nil{ queueappend(queue,curNode.Right) } } ansappend(ans,res)//当前层节点压入ans } return ans }1.2二叉树的中序遍历以下是递归的代码思路就是先递归左子树诺左子树不存在就回溯上一层把当前节点压入结果数组切片接着递归右子树中序遍历是三种遍历中最实用的需要重点掌握因为它能和搜索二叉树相联系func inorderTraversal(root *TreeNode) []int { var ans []int var midOrder func(*TreeNode) midOrderfunc(node *TreeNode){ if nodenil{ return } midOrder(node.Left)//递归左子树 ansappend(ans,node.Val) midOrder(node.Right)//递归右子树 } midOrder(root) return ans }非递归代码如下,func inorderTraversal(root *TreeNode) []int { var ans []int var stack []*TreeNode cur : root for cur ! nil || len(stack) 0 { // 不断向左走并将经过的节点入栈 for cur ! nil { stack append(stack, cur) cur cur.Left } // 此时 cur 为 nil说明到达最左端弹出栈顶节点并访问 cur stack[len(stack)-1] stack stack[:len(stack)-1] ans append(ans, cur.Val) // 转向右子树继续下一次循环 cur cur.Right } return ans }大家可以根据这个例子思考一下递归跟栈的关系1.3二叉树先序遍历递归写法如下func preorderTraversal(root *TreeNode) []int { var ans []int var preOrder func(*TreeNode) preOrder func(node *TreeNode) { if node nil { return } ans append(ans, node.Val) // 访问根 preOrder(node.Left) // 左子树 preOrder(node.Right) // 右子树 } preOrder(root) return ans }非递归写法func preorderTraversal(root *TreeNode) []int { var ans []int stack : []*TreeNode{} cur : root for cur ! nil || len(stack) 0 { // 一路向左访问根节点并入栈 for cur ! nil { ans append(ans, cur.Val) // 先序访问根 stack append(stack, cur) cur cur.Left } // 弹出栈顶转向右子树 cur stack[len(stack)-1] stack stack[:len(stack)-1] cur cur.Right } return ans }1.4二叉树的后序遍历递归代码如下func postorderTraversal(root *TreeNode) []int { var ans []int var postOrder func(*TreeNode) postOrder func(node *TreeNode) { if node nil { return } postOrder(node.Left) postOrder(node.Right) ans append(ans, node.Val) // 最后访问根 } postOrder(root) return ans }非递归写法如下func postorderTraversal(root *TreeNode) []int { var ans []int stack : []*TreeNode{} var prev *TreeNode // 记录上一个被访问的节点 cur : root for cur ! nil || len(stack) 0 { // 一路向左只入栈不访问 for cur ! nil { stack append(stack, cur) cur cur.Left } // 查看栈顶暂不弹出 cur stack[len(stack)-1] // 如果右子树为空或者右子树刚刚被访问过则可以访问当前根节点 if cur.Right nil || cur.Right prev { ans append(ans, cur.Val) // 后序访问根 stack stack[:len(stack)-1] prev cur // 标记当前节点已访问 cur nil // 让下一轮循环直接弹出栈顶回溯 } else { // 否则先处理右子树 cur cur.Right } } return ans }不论是递归方法还是非递归写法都需要熟练掌握不要觉得递归代码少就只掌握递归方式书到用时方恨少。2.树的基础题2.1二叉树的最大深度这道题就是一道很基本的递归记录当前的深度然后将其与最大深度进行比较就不多说了。func maxDepth(root *TreeNode) int { var deep0 var dfs func(*TreeNode,int) dfsfunc(node *TreeNode,curdeep int){ if nodenil{ return } curdeep deepmax(deep,curdeep) dfs(node.Left,curdeep) dfs(node.Right,curdeep) } dfs(root,0) return deep }2.2翻转二叉树代码也很简单就是不断交换左右子树。func invertTree(root *TreeNode) *TreeNode { if rootnil{ return nil } root.Left,root.Rightroot.Right,root.Left//交换左右子树 invertTree(root.Left) invertTree(root.Right) return root }2.3.对称二叉树看一颗树是否对称就是看它的左子树和右子树是否相同或者说两者镜像对称那么判断两子树是否相同就是判断左子树的左子树和右子树的右子树是否相同又是一道递归题稍微有点难度关键是想到递归的点具体细节写在代码中注意当两个子节点非空且相等时我们不返回true而是接着向下递归原因是我们要判断的是整棵树是否对称而不是一个节点。func isSymmetric(root *TreeNode) bool { var isSym func(*TreeNode,*TreeNode)bool isSymfunc(left *TreeNode,right *TreeNode)bool{ if rightnilleftnil{//说明已经判断完了一条路径 return true } if (right!nilleftnil)||(rightnilleft!nil){//一定不对称 return false } if right!nilleft!nil{ if right.Val!left.Val{ return false } //相等时接着递归不返回true } flag1:isSym(left.Left,right.Right) flag2:isSym(left.Right,right.Left) return flag1flag2 } return isSym(root.Left,root.Right) }2.4二叉树的直径与其说这道题是递归到不如说是回溯因为本质上我们在遍历到叶子节点的过程中我们其实什么都没做反倒是在从叶子结点回溯到根节点的过程中不断记录最大路径的长度也很好理解因为如果从根节点开始记录路径长度的话那么你的每条路径必然会经过根节点但实际上最长路径不一定会经过根节点完整代码如下func diameterOfBinaryTree(root *TreeNode) int { var ans int var dfs func(*TreeNode,*int)int dfsfunc(node *TreeNode,ans *int)int{ if nodenil{ return -1 } leftLen:dfs(node.Left,ans)1 rightLen:dfs(node.Right,ans)1 *ansmax(*ans,leftLenrightLen) return max(leftLen,rightLen) } dfs(root,ans) return ans }2.5.将有序数组转换为二叉搜索树二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树:若它的左子树不为空则左子树上所有结点的值都小于等于根结点的值若它的右子树不为空则右子树上所有结点的值都大于等于根结点的值.它的左右子树也分别为二叉搜索树在了解了什么是二叉搜索树后这道题的具体思路也就出来了数组中间的元素肯定是根节点那么根节点的左子树的各个节点一定在数组的左半部分右子树的各个节点一定在数组的右半部分那么对于左子树的左子树也就一定在数组左半部分的左半部分左子树的右子树一定在数组的左半部分的右半部分那么递归场景就被我们刻画出来了完整代码如下。func sortedArrayToBST(nums []int) *TreeNode { if len(nums)0{ return nil } root:TreeNode{ Val:nums[len(nums)/2], } root.LeftsortedArrayToBST(nums[0:len(nums)/2]) root.RightsortedArrayToBST(nums[len(nums)/21:]) return root }2.6验证二叉搜索树如果你观察仔细就会发现二叉搜索树的中序遍历会是一个递增的数组那么利用这一特性我们只需要把该二叉树按中序遍历出来判断它是否递增即可怎么判断呢只需要将当前元素与前一个元素比较因此我们需要定义一个变量pre来保存前一个元素func isValidBST(root *TreeNode) bool { if rootnil{ return true } var stack []*TreeNode var cur *TreeNoderoot pre:math.MinInt for cur!nil||len(stack)0{ for cur!nil{ stackappend(stack,cur) curcur.Left } curstack[len(stack)-1] stackstack[:len(stack)-1] if cur.Valpre{ return false } precur.Val curcur.Right } return true }2.7二叉搜索树中第k小的元素我们依旧按中序遍历遍历二叉树遍历到第k个元素就返回。完整代码如下func kthSmallest(root *TreeNode, k int) int { var cur *TreeNoderoot var stack []*TreeNode var n0 for cur!nil||len(stack)0{ for cur!nil{ stackappend(stack,cur) curcur.Left } curstack[len(stack)-1] stackstack[:len(stack)-1] n if nk{ return cur.Val } curcur.Right } return 0 }2.8二叉树的右视图其实就是返回二叉树每一层最右侧的元素也就是最后一个元素我们用层序遍历来写func rightSideView(root *TreeNode) []int { if root nil { return []int{} } var ans []int var queue []*TreeNode queue append(queue, root) for len(queue) 0 { size : len(queue) var curList []*TreeNode for i:0;isize;i{ curNode:queue[0] queuequeue[1:] curListappend(curList,curNode) if curNode.Left!nil{ queueappend(queue,curNode.Left) } if curNode.Right!nil{ queueappend(queue,curNode.Right) } } ansappend(ans,curList[len(curList)-1].Val) } return ans }3.树的进阶题3.1.二叉树展开为链表主要是先序遍历的非递归写法把每个节点按先序遍历的顺序存入一个数组再按把它们连成链表就可以了func flatten(root *TreeNode) { if rootnil{ return } //前序遍历收集节点 cur:root var stack []*TreeNode var nodeList []*TreeNode for cur!nil||len(stack)0{ for cur!nil{ nodeListappend(nodeList,cur) stackappend(stack,cur) curcur.Left } cur stack[len(stack)-1] stackstack[:len(stack)-1] curcur.Right } for i:0;ilen(nodeList)-1;i{ nodeList[i].Leftnil nodeList[i].RightnodeList[i1] } nodeList[len(nodeList)-1].Leftnil nodeList[len(nodeList)-1].Rightnil }递归写法相对来讲没那么好理解但也还行func flatten(root *TreeNode) { if rootnil{ return } flatten(root.Left) flatten(root.Left) dummy:root.Right root.Rightroot.Left root.Leftnil var tem_rootroot for tem_root.Right!nil{ tem_roottem_root.Right } tem_root.Rightdummy }3.2.从前序遍历和中序遍历构造二叉树这道题跟2.5挺像的主要是注意前序遍历根左右和中序遍历左根右所以可以根据前序遍历来确定每个根节点左右子树的范围找到前序遍历根节点在中序遍历的index再分别确定左右子树在前序遍历和中序遍历数组中的范围func buildTree(preorder []int, inorder []int) *TreeNode { if len(preorder)0||len(inorder)0{ return nil } root:TreeNode{ Val:preorder[0], } index:0 for preorder[0]!inorder[index]{ index } root.LeftbuildTree(preorder[1:index1],inorder[:index]) root.RightbuildTree(preorder[1index:],inorder[index1:]) return root }3.3.路径总和III这道题就是深度优先搜索找目标值然后广度优先搜索去遍历每个节点比较综合。完整代码如下func pathSum(root *TreeNode, targetSum int) int { if rootnil{ return 0 } var ans 0 var dfs func(*TreeNode,int) dfsfunc(node *TreeNode,sum int){ if nodenil{ return } sumnode.Val//加上当前节点的值 if sumtargetSum{ ans//不返回可能有多个路径满足答案 } dfs(node.Left,sum) dfs(node.Right,sum) } var queue []*TreeNode queueappend(queue,root) for len(queue)0{ size:len(queue) for i:0;isize;i{ curNode:queue[0] queuequeue[1:] dfs(curNode,0) if curNode.Left!nil{ queueappend(queue,curNode.Left) } if curNode.Right!nil{ queueappend(queue,curNode.Right) } } } return ans }3.4.二叉树的最近公共祖先本质上就是分别找根节点到指定两个节点的路径把路径分别存在两个数组中那么数组中最后相等的元素就是两者的最近公共祖先完整代码如下func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode { var ans *TreeNode var p_path []*TreeNode var q_path []*TreeNode var path []*TreeNode var dfs func(*TreeNode,[]*TreeNode) dfs func(node *TreeNode,path []*TreeNode) { if node nil || (len(p_path) 0 len(q_path) 0) { return } pathappend(path,node) if nodep{ tmp:make([]*TreeNode,len(path)) copy(tmp,path) p_pathtmp } if nodeq{ tmp:make([]*TreeNode,len(path)) copy(tmp,path) q_pathtmp } dfs(node.Left,path) dfs(node.Right,path) } dfs(root,path) for i:0;imin(len(p_path),len(q_path));i{ if p_path[i]q_path[i]{ ansp_path[i] }else{ break } } return ans }3.5.二叉树中的最大路径和其实本质上和二叉树的直径是同一道题只不过从找左右节点的最大路径长度改成了找左右节点的最大值func maxPathSum(root *TreeNode) int { var ans root.Val var dfs func(*TreeNode) int dfsfunc(node *TreeNode) int{ if nodenil{ return 0 } lmax:max(0,dfs(node.Left)) rmax:max(0,dfs(node.Right)) ansmax(ans,lmaxrmaxnode.Val) return node.Valmax(lmax,rmax) } dfs(root) return ans }