小白水平理解面试经典题目LeetCode 655. Print Binary Tree【Tree】

2024-02-28 16:04

本文主要是介绍小白水平理解面试经典题目LeetCode 655. Print Binary Tree【Tree】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

655 打印二叉树

一、小白翻译

给定二叉树的 root ,构造一个 0 索引的 m x n 字符串矩阵 res 来表示树的格式化布局。格式化布局矩阵应使用以下规则构建:

  • 树的高度为 height ,行数 m 应等于 height + 1 。

  • 列数 n 应等于​​xheight+1​​ - 1 。

  • 将根节点放置在顶行的中间(更正式地说,位于位置 res[0][(n-1)/2] )。

  • 对于已放置在矩阵中位置 res[r][c] 的每个节点,将其左子节点放置在 res[r+1][c-2height-r-1] 处,将其右子节点放置在 res[r+1][c+2height-r-1] 处。

  • 继续此过程,直到树中的所有节点都已放置完毕。

  • 任何空单元格都应包含空字符串 “” 。

返回构造的矩阵 res 。

二、例子

在这里插入图片描述
在这里插入图片描述
限制条件
在这里插入图片描述

这里是小白理解

这种题目我们首先把他进行下条件梳理
这时候黑长直女神过来问:小白,你这题怎么思考的啊?
小白内心镇定:小美,马上春天了,有机会一起去公园出大片吧?
在这里插入图片描述
哦,不是,这道题咱们可以考虑下用递归算法 + 画图来辅助做题
这里我拿一个三层的树进行举例子。
在这里插入图片描述
我们如果在这样画出来就更加直观的看出来每个值的位置。
[
 [“”, “”, “”, “1”, “”, “”, “”],
 [“”, “2”, “”, “”, “”, “3”, “”],
 [“4”, “”, “5”, “”, “”, “”, “”]
]

  • 首先,我们需要计算出二叉树的高度,以便确定矩阵的行数。
  • 然后,我们可以根据高度计算出矩阵的列数,即 2height-1
  • 接下来,我们可以使用递归的方法来遍历二叉树,并将每个节点的值填充到矩阵中。
  • 在递归过程中,我们需要根据当前节点的位置来计算其在矩阵中的行列号。
  • 对于每个节点,我们需要将其值填充到矩阵中,并将其左右子树分别递归地打印到矩阵的左右两部分。

小美:小伙子,可以啊,这不仅逻辑感人,阅读理解也有俩下子, 不过要是照的不美可有你好看了!

小白:没问题,谁叫为了“真爱”呢。

在这里插入图片描述

真正面试环节

面试官:你可以解答这道”融合链表“的题目吗,来看看你对二叉树结构的理解。

小白:嘿嘿,这不巧了么这不是

在这里插入图片描述

    public List<List<String>> printTree(TreeNode root) {int height = getHeight(root); // 树的高度int width = (1 << height) - 1; // 总的列数List<List<String>> res = new ArrayList<>();// 给出整个矩阵for (int i = 0; i < height; i++) {List<String> row = new ArrayList<>();for (int j = 0; j < width; j++) {row.add("");}res.add(row);}printTree(root, res, 0, 0, width - 1);return res;}// 算出树高度private int getHeight(TreeNode root) {if (root == null) {return 0;}return Math.max(getHeight(root.left), getHeight(root.right)) + 1;}private void printTree(TreeNode root, List<List<String>> res, int row, int start, int end) {if (root == null) {return;}int mid = (start + end) / 2;res.get(row).set(mid, String.valueOf(root.val));// 对左侧子树进行计算printTree(root.left, res, row + 1, start, mid - 1);// 对右侧子树进行计算printTree(root.right, res, row + 1, mid + 1, end);}

这里的宽度采用了位运算

为了不熟悉位运算的,这里用个例子便于大家理解。
1 << 3 代表的意思是 “1的二进制数左移3项”
0001 1000
 1   8

小明:OK,完事儿,等着面试官来表扬自己吧。他肯定会说:小子,你是个好手!工位都给你准备好了,工资你说了算。

面试官:矮油,不错啊,不过你这能不能写个测试啊。

小明OS:今年这个找工市场,人言洛阳花似锦,偏我来时不逢春。。。不是,怎么还让我些test case 啊!
总结

	public static void main(String[] args) {TreeNode root = new TreeNode(1);root.left = new TreeNode(2);root.right = new TreeNode(3);root.left.left = new TreeNode(4);root.left.right = new TreeNode(5);printBinaryTree655 solution = new printBinaryTree655();List<List<String>> res = solution.printTree(root);for (List<String> row : res) {for (String s : row) {System.out.print(s + " ");}System.out.println();}}

小白:您好,面试官,这回可以了吧,我终于可以开心练摄影技术为小美照相了!
在这里插入图片描述

============================================================================
🍀🍀🍀🍀🍀🍀更多算法题解请看 面试数据结构与算法总结分类+leetcode目录【基础版】
编码道路漫漫,只要先看脚下的路,徐徐前进即可。

这篇关于小白水平理解面试经典题目LeetCode 655. Print Binary Tree【Tree】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/755962

相关文章

CSS @media print 使用详解

《CSS@mediaprint使用详解》:本文主要介绍了CSS中的打印媒体查询@mediaprint包括基本语法、常见使用场景和代码示例,如隐藏非必要元素、调整字体和颜色、处理链接的URL显示、分页控制、调整边距和背景等,还提供了测试方法和关键注意事项,并分享了进阶技巧,详细内容请阅读本文,希望能对你有所帮助...

深入理解Apache Airflow 调度器(最新推荐)

《深入理解ApacheAirflow调度器(最新推荐)》ApacheAirflow调度器是数据管道管理系统的关键组件,负责编排dag中任务的执行,通过理解调度器的角色和工作方式,正确配置调度器,并... 目录什么是Airflow 调度器?Airflow 调度器工作机制配置Airflow调度器调优及优化建议最

一文带你理解Python中import机制与importlib的妙用

《一文带你理解Python中import机制与importlib的妙用》在Python编程的世界里,import语句是开发者最常用的工具之一,它就像一把钥匙,打开了通往各种功能和库的大门,下面就跟随小... 目录一、python import机制概述1.1 import语句的基本用法1.2 模块缓存机制1.

深入理解C语言的void*

《深入理解C语言的void*》本文主要介绍了C语言的void*,包括它的任意性、编译器对void*的类型检查以及需要显式类型转换的规则,具有一定的参考价值,感兴趣的可以了解一下... 目录一、void* 的类型任意性二、编译器对 void* 的类型检查三、需要显式类型转换占用的字节四、总结一、void* 的

深入理解Redis大key的危害及解决方案

《深入理解Redis大key的危害及解决方案》本文主要介绍了深入理解Redis大key的危害及解决方案,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着... 目录一、背景二、什么是大key三、大key评价标准四、大key 产生的原因与场景五、大key影响与危

深入理解C++ 空类大小

《深入理解C++空类大小》本文主要介绍了C++空类大小,规定空类大小为1字节,主要是为了保证对象的唯一性和可区分性,满足数组元素地址连续的要求,下面就来了解一下... 目录1. 保证对象的唯一性和可区分性2. 满足数组元素地址连续的要求3. 与C++的对象模型和内存管理机制相适配查看类对象内存在C++中,规

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

字节面试 | 如何测试RocketMQ、RocketMQ?

字节面试:RocketMQ是怎么测试的呢? 答: 首先保证消息的消费正确、设计逆向用例,在验证消息内容为空等情况时的消费正确性; 推送大批量MQ,通过Admin控制台查看MQ消费的情况,是否出现消费假死、TPS是否正常等等问题。(上述都是临场发挥,但是RocketMQ真正的测试点,还真的需要探讨) 01 先了解RocketMQ 作为测试也是要简单了解RocketMQ。简单来说,就是一个分

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

uva 575 Skew Binary(位运算)

求第一个以(2^(k+1)-1)为进制的数。 数据不大,可以直接搞。 代码: #include <stdio.h>#include <string.h>const int maxn = 100 + 5;int main(){char num[maxn];while (scanf("%s", num) == 1){if (num[0] == '0')break;int len =