树的相关算法

关于树的算法，本人认为主要就是记住树的各种遍历（中序遍历，先序遍历，后序遍历和层序遍历），本质上也就是要求你掌握深度优先搜索和广度优先搜索。树的深度优先搜索可以用递归和栈两种方法来实现（递归本质就是压栈出栈的过程），层序遍历（广度优先搜索）一般用队列实现。其实一般到图论，我们才讲深度优先搜索和广度优先搜索，但树也是图的一种嘛，博主就这样说了，注意写树的题目不要太在意递归的细节，这样可能会把自己绕进去。当你掌握了以上两种算法，相信树的大部分算法你就都能解决了。

1.树的遍历方式

1.1二叉树的层序遍历

这个代码没什么讲得，就是用队列存储当前层的代码，然后在遍历当前层的结点的同时，加入下一层结点，把当前层的结点全部压入ans就行了，看不懂的同学就自己拿草稿纸一步步推算吧，大家都是这么过来的

func levelOrder(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 res []int//存储当前层的结点的值 for i:=0;i<size;i++{ curNode:=queue[0] queue=queue[1:] res=append(res,curNode.Val) //下一层节点压入队列 if curNode.Left!=nil{ queue=append(queue,curNode.Left) } if curNode.Right!=nil{ queue=append(queue,curNode.Right) } } ans=append(ans,res)//当前层节点压入ans } return ans }

1.2二叉树的中序遍历

以下是递归的代码，思路就是先递归左子树，诺左子树不存在就回溯上一层把当前节点压入结果数组（切片），接着递归右子树，中序遍历是三种遍历中最实用的，需要重点掌握，因为它能和搜索二叉树相联系

func inorderTraversal(root *TreeNode) []int { var ans []int var midOrder func(*TreeNode) midOrder=func(node *TreeNode){ if node==nil{ return } midOrder(node.Left)//递归左子树 ans=append(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 deep=0 var dfs func(*TreeNode,int) dfs=func(node *TreeNode,curdeep int){ if node==nil{ return } curdeep++ deep=max(deep,curdeep) dfs(node.Left,curdeep) dfs(node.Right,curdeep) } dfs(root,0) return deep }

2.2翻转二叉树

代码也很简单，就是不断交换左右子树。

func invertTree(root *TreeNode) *TreeNode { if root==nil{ return nil } root.Left,root.Right=root.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 isSym=func(left *TreeNode,right *TreeNode)bool{ if right==nil&&left==nil{//说明已经判断完了一条路径 return true } if (right!=nil&&left==nil)||(right==nil&&left!=nil){//一定不对称 return false } if right!=nil&&left!=nil{ if right.Val!=left.Val{ return false } //相等时接着递归不返回true } flag1:=isSym(left.Left,right.Right) flag2:=isSym(left.Right,right.Left) return flag1&&flag2 } return isSym(root.Left,root.Right) }

2.4二叉树的直径

与其说这道题是递归，到不如说是回溯，因为本质上，我们在遍历到叶子节点的过程中，我们其实什么都没做，反倒是在从叶子结点回溯到根节点的过程中，不断记录最大路径的长度，也很好理解，因为如果从根节点开始记录路径长度的话，那么你的每条路径必然会经过根节点，但实际上，最长路径不一定会经过根节点，完整代码如下

func diameterOfBinaryTree(root *TreeNode) int { var ans int var dfs func(*TreeNode,*int)int dfs=func(node *TreeNode,ans *int)int{ if node==nil{ return -1 } leftLen:=dfs(node.Left,ans)+1 rightLen:=dfs(node.Right,ans)+1 *ans=max(*ans,leftLen+rightLen) 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.Left=sortedArrayToBST(nums[0:len(nums)/2]) root.Right=sortedArrayToBST(nums[len(nums)/2+1:]) return root }

2.6验证二叉搜索树

如果你观察仔细就会发现，二叉搜索树的中序遍历会是一个递增的数组，那么利用这一特性，我们只需要把该二叉树按中序遍历出来，判断它是否递增即可，怎么判断呢，只需要将当前元素与前一个元素比较，因此我们需要定义一个变量pre来保存前一个元素

func isValidBST(root *TreeNode) bool { if root==nil{ return true } var stack []*TreeNode var cur *TreeNode=root pre:=math.MinInt for cur!=nil||len(stack)>0{ for cur!=nil{ stack=append(stack,cur) cur=cur.Left } cur=stack[len(stack)-1] stack=stack[:len(stack)-1] if cur.Val<=pre{ return false } pre=cur.Val cur=cur.Right } return true }

2.7二叉搜索树中第k小的元素

我们依旧按中序遍历遍历二叉树，遍历到第k个元素就返回。完整代码如下

func kthSmallest(root *TreeNode, k int) int { var cur *TreeNode=root var stack []*TreeNode var n=0 for cur!=nil||len(stack)>0{ for cur!=nil{ stack=append(stack,cur) cur=cur.Left } cur=stack[len(stack)-1] stack=stack[:len(stack)-1] n++ if n==k{ return cur.Val } cur=cur.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;i<size;i++{ curNode:=queue[0] queue=queue[1:] curList=append(curList,curNode) if curNode.Left!=nil{ queue=append(queue,curNode.Left) } if curNode.Right!=nil{ queue=append(queue,curNode.Right) } } ans=append(ans,curList[len(curList)-1].Val) } return ans }

3.树的进阶题

3.1.二叉树展开为链表

主要是先序遍历的非递归写法，把每个节点按先序遍历的顺序存入一个数组，再按把它们连成链表就可以了

func flatten(root *TreeNode) { if root==nil{ return } //前序遍历收集节点 cur:=root var stack []*TreeNode var nodeList []*TreeNode for cur!=nil||len(stack)>0{ for cur!=nil{ nodeList=append(nodeList,cur) stack=append(stack,cur) cur=cur.Left } cur = stack[len(stack)-1] stack=stack[:len(stack)-1] cur=cur.Right } for i:=0;i<len(nodeList)-1;i++{ nodeList[i].Left=nil nodeList[i].Right=nodeList[i+1] } nodeList[len(nodeList)-1].Left=nil nodeList[len(nodeList)-1].Right=nil }

递归写法，相对来讲没那么好理解，但也还行

func flatten(root *TreeNode) { if root==nil{ return } flatten(root.Left) flatten(root.Left) dummy:=root.Right root.Right=root.Left root.Left=nil var tem_root=root for tem_root.Right!=nil{ tem_root=tem_root.Right } tem_root.Right=dummy }

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.Left=buildTree(preorder[1:index+1],inorder[:index]) root.Right=buildTree(preorder[1+index:],inorder[index+1:]) return root }

3.3.路径总和III

这道题就是深度优先搜索找目标值，然后广度优先搜索去遍历每个节点，比较综合。

完整代码如下

func pathSum(root *TreeNode, targetSum int) int { if root==nil{ return 0 } var ans =0 var dfs func(*TreeNode,int) dfs=func(node *TreeNode,sum int){ if node==nil{ return } sum+=node.Val//加上当前节点的值 if sum==targetSum{ ans++//不返回，可能有多个路径满足答案 } dfs(node.Left,sum) dfs(node.Right,sum) } var queue []*TreeNode queue=append(queue,root) for len(queue)>0{ size:=len(queue) for i:=0;i<size;i++{ curNode:=queue[0] queue=queue[1:] dfs(curNode,0) if curNode.Left!=nil{ queue=append(queue,curNode.Left) } if curNode.Right!=nil{ queue=append(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 } path=append(path,node) if node==p{ tmp:=make([]*TreeNode,len(path)) copy(tmp,path) p_path=tmp } if node==q{ tmp:=make([]*TreeNode,len(path)) copy(tmp,path) q_path=tmp } dfs(node.Left,path) dfs(node.Right,path) } dfs(root,path) for i:=0;i<min(len(p_path),len(q_path));i++{ if p_path[i]==q_path[i]{ ans=p_path[i] }else{ break } } return ans }

3.5.二叉树中的最大路径和

其实本质上和二叉树的直径是同一道题，只不过从找左右节点的最大路径长度改成了找左右节点的最大值

func maxPathSum(root *TreeNode) int { var ans = root.Val var dfs func(*TreeNode) int dfs=func(node *TreeNode) int{ if node==nil{ return 0 } lmax:=max(0,dfs(node.Left)) rmax:=max(0,dfs(node.Right)) ans=max(ans,lmax+rmax+node.Val) return node.Val+max(lmax,rmax) } dfs(root) return ans }