输出二叉树

简介: #### [655. 输出二叉树](https://leetcode.cn/problems/print-binary-tree/)

一、题目描述:

给你一棵二叉树的根节点 root ,请你构造一个下标从 0 开始、大小为 m x n 的字符串矩阵 res ,用以表示树的 格式化布局 。构造此格式化布局矩阵需要遵循以下规则:

树的 高度 为 height ,矩阵的行数 m 应该等于 height + 1 。
矩阵的列数 n 应该等于 2height+1 - 1 。
根节点 需要放置在 顶行 的 正中间 ,对应位置为 res0 。
对于放置在矩阵中的每个节点,设对应位置为 resr ,将其左子节点放置在 resr+1 ,右子节点放置在 resr+1 。
继续这一过程,直到树中的所有节点都妥善放置。
任意空单元格都应该包含空字符串 "" 。
返回构造得到的矩阵 res 。

示例 1:

img

输入:root = [1,2]
输出:
[["","1",""],
["2","",""]]
示例 2:

img

输入:root = [1,2,3,null,4]
输出:
[["","","","1","","",""],
["","2","","","","3",""],
["","","4","","","",""]]

提示:

树中节点数在范围 [1, 210] 内
-99 <= Node.val <= 99
树的深度在范围 [1, 10] 内

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/print-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

二、思路分析:

采用DFS+分治的思想,先通过DFS获取树的高度,确定好每一行里面有多少个元素:2^树高-1;
再采用分治的思想去确定每一行应该输出在哪个位置,根节点输出在mid=(low+high)/2处,左孩子输出在[low,mid-1]的中间,右孩子输出在[mid+1,high]的中间,其中low初始为0,high初始为每一行元素的个数-1(因为在数组中对应索引为最大元素个数-1);
直至全部元素输出完成;

三、AC 代码:

public class Solution {
    public List<List<String>> printTree(TreeNode root) {
        int height = getHeight(root);
        String[][] res = new String[height][(1 << height) - 1];
        for(String[] arr:res)
            Arrays.fill(arr,"");
        List<List<String>> ans = new ArrayList<>();
        fill(res, root, 0, 0, res[0].length);
        for(String[] arr:res)
            ans.add(Arrays.asList(arr));
        return ans;
    }
    public void fill(String[][] res, TreeNode root, int i, int l, int r) {
        if (root == null)
            return;
        res[i][(l + r) / 2] = "" + root.val;
        fill(res, root.left, i + 1, l, (l + r) / 2);
        fill(res, root.right, i + 1, (l + r + 1) / 2, r);
    }
    public int getHeight(TreeNode root) {
        if (root == null)
            return 0;
        return 1 + Math.max(getHeight(root.left), getHeight(root.right));
    }
}

四、总结:

image.png

掘友们,解题不易,留下个赞或评论再走吧!谢啦~ 💐

希望对你有帮助

期待下次再见~

相关文章
|
30天前
输入二叉树先序序列,输出先序,中序,后序序列
输入二叉树先序序列,输出先序,中序,后序序列
13 0
剑指offer_二叉树---之字形打印二叉树
剑指offer_二叉树---之字形打印二叉树
58 0
剑指offer_二叉树---从上往下打印二叉树
剑指offer_二叉树---从上往下打印二叉树
65 0
剑指offer_二叉树---把二叉树打印成多行
剑指offer_二叉树---把二叉树打印成多行
61 0
剑指offer_二叉树---二叉树中和为某一值的路径
剑指offer_二叉树---二叉树中和为某一值的路径
77 0
|
算法
【算法】二叉排序树:创建二叉树,并以中序遍历输出
【算法】二叉排序树:创建二叉树,并以中序遍历输出
214 0
代码随想录刷题|LeetCode 513. 找树左下角的值 112. 路径总和 113.路径总和|| 106. 从中序与后序遍历序列构造二叉树 105.从前序与中序遍历序列构造二叉树
代码随想录刷题|LeetCode 513. 找树左下角的值 112. 路径总和 113.路径总和|| 106. 从中序与后序遍历序列构造二叉树 105.从前序与中序遍历序列构造二叉树
代码随想录刷题|LeetCode 513. 找树左下角的值 112. 路径总和 113.路径总和|| 106. 从中序与后序遍历序列构造二叉树 105.从前序与中序遍历序列构造二叉树
先序序列创建二叉树,输出先序序列、中序序列、后序序列并输出叶子结点数
先序序列创建二叉树,输出先序序列、中序序列、后序序列并输出叶子结点数
579 0
先序序列创建二叉树,输出先序序列、中序序列、后序序列并输出叶子结点数
7-10 先序序列创建二叉树,输出先序序列、中序序列、后序序列并输出叶子结点数 (10 分)
7-10 先序序列创建二叉树,输出先序序列、中序序列、后序序列并输出叶子结点数 (10 分)
425 0
7-10 先序序列创建二叉树,输出先序序列、中序序列、后序序列并输出叶子结点数 (10 分)