本次刷题日记的第 104 篇，力扣题为：655. 输出二叉树
一、题目描述：
继续做每日一题，输出一个二叉树，看看和其他二叉树的题目有何不同
二、这道题考察了什么思想？你的思路是什么？
仔细看看题目对我们有啥子要求，并不是简单的去处理一颗二叉树的问题这么简单了哦
- 题目要求我们找到给出二叉树的深度 height ，深度从 0 开始的
- 需要我们将二叉树画到矩阵中，矩阵的行为 height+1， 列为 1<<(height+1) -1
- 对于根节点我们需要画在第 0 行的 (列-1)/2
- 对于一个节点的左节点，我们需要画在下一行的左侧 row+1,col-1<<(height - row -1)
- 右节点我们需要画在下一行的右侧，row+1,col+1<<(height - row -1)
分析
那么这个时候我们如何来将一颗二叉树，转换成一个字符串的矩阵呢？
实际上分析这个题的大方向就两件事情
- 第一，想办法获取树的高度，我们可以通过深度优先算法（递归），或者广度优先算法（队列）都是可以看，看我们自己对哪个更加熟悉
- 第二，遍历二叉树节点的时候，知道要将这个节点放到哪个位置，那么遍历到节点的时候，咱们就要带上具体的行列值，也可以是相关值，只要能计算出具体的节点坐标就可以
第一件事情比较常规和简单，我们就不多赘述了
对于第二件事情的话，我们就推演一个深度优先算法的，例如对于一个如下图的二叉树
暂时无法在文档外展示此内容
如果层数较多，一样的按照上述题目给出的条件和公式向下递归即可，那么接下来咱们就来手撸代码吧
三、编码
根据上述逻辑和分析，我们就可以翻译成如下代码
- 通过深度优先算法递归获取二叉树的高度 height
- 初始化咱们的矩阵，行为 height+1，列为 1<<(height+1) -1
- 开始递归遍历二叉树，对于遍历到的节点，咱们将值转换成字符串赋值到矩阵对应的位置即可
编码如下：
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func getHeight(root *TreeNode) int { height := 0 if root.Left != nil { height = getHeight(root.Left) +1 } if root.Right != nil { height = max(getHeight(root.Right) +1, height) } return height } func max(a,b int) int { if a>b { return a } return b } func printTree(root *TreeNode) [][]string { // 获取 二叉树的高度 height := getHeight(root) // 定义结果数组 res := make([][]string, height+1) n := 1<<(height+1) -1 for i:=0; i<height+1; i++ { // 开辟空间的默认值就是 空字符串 res[i] = make([]string, n) } // 遍历 var dfs func(*TreeNode, int, int) dfs = func(root *TreeNode, row int, col int) { // 将具体的数值转成字符串 res[row][col] = strconv.Itoa(root.Val) // 操作左节点 if root.Left != nil{ dfs(root.Left, row+1, col-1<<(height-row-1)) } // 操作右节点 if root.Right != nil{ dfs(root.Right, row+1, col+1<<(height-row-1)) } } dfs(root, 0, (n-1)/2) return res }
四、总结：
本次咱们这种处理方式是使用了深度优先算法，空间复杂度实际上主要是咱们进行递归消耗的栈空间，应该是 O(height)
时间复杂度是O(height*2^height)， 此处这个是因为咱们需要去填充矩阵中每一个空间的值，因此空间复杂度是这个数
原题地址：655. 输出二叉树
欢迎点赞，关注，收藏
朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力
好了，本次就到这里
技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。
我是阿兵云原生，欢迎点赞关注收藏，下次见~
