网站建设公司相关资质,济南全包圆装修400电话,长沙 外贸网站建设公司排名,石家庄视频优化公司输出二叉树 题目描述代码演示 题目描述 难度 - 中等 leetcode 655. 输出二叉树 给你一棵二叉树的根节点 root #xff0c;请你构造一个下标从 0 开始、大小为 m x n 的字符串矩阵 res #xff0c;用以表示树的 格式化布局 。构造此格式化布局矩阵需要遵循以下规则#xff1a… 输出二叉树 题目描述代码演示 题目描述 难度 - 中等 leetcode 655. 输出二叉树 给你一棵二叉树的根节点 root 请你构造一个下标从 0 开始、大小为 m x n 的字符串矩阵 res 用以表示树的 格式化布局 。构造此格式化布局矩阵需要遵循以下规则 树的 高度 为 height 矩阵的行数 m 应该等于 height 1 。 矩阵的列数 n 应该等于 2height1 - 1 。 根节点 需要放置在 顶行 的 正中间 对应位置为 res[0][(n-1)/2] 。 对于放置在矩阵中的每个节点设对应位置为 res[r][c] 将其左子节点放置在 res[r1][c-2height-r-1] 右子节点放置在 res[r1][c2height-r-1] 。 继续这一过程直到树中的所有节点都妥善放置。 任意空单元格都应该包含空字符串 “” 。 返回构造得到的矩阵 res 。 示例1 输入root [1,2] 输出 [[“”,“1”,“”], [“2”,“”,“”]] 示例2: 输入root [1,2,3,null,4] 输出 [[“”,“”,“”,“1”,“”,“”,“”], [“”,“2”,“”,“”,“”,“3”,“”], [“”,“”,“4”,“”,“”,“”,“”]] 提示 树中节点数在范围 [1, 210] 内 -99 Node.val 99 树的深度在范围 [1, 10] 内 ## 递归 根据题意我们可以先设计 dfs1 递归函数得到树的高度 h以及与其相关的矩阵行列大小并初始化矩阵。 随后根据填充规则设计 dfs2 递归函数往矩阵进行填充。 代码演示
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {int h,m,n;ListListString ans;public ListListString printTree(TreeNode root) {dfsH(root,0);m h 1;n (1 (h 1)) - 1;ans new ArrayList();//填充值for(int i 0; i m;i){ListString tmp new ArrayList();for(int j 0; j n;j){tmp.add(); }ans.add(tmp);}dfsF(root,0,n / 2);return ans;}//DFS 计算树的高度void dfsH(TreeNode root,int depth){if(root null){return ;}h Math.max(h,depth);dfsH(root.left,depth 1);dfsH(root.right,depth 1);}//填充值void dfsF(TreeNode root,int r,int c){if(root null){return;}ans.get(r).set(c,root.val);dfsF(root.left,r 1,c - (1 (h - r - 1)));dfsF(root.right,r 1,c (1 (h - r - 1)));}
}
