LeetCode 655. Print Binary Tree

问题描述



将一颗二叉树以 m*n 二维数组的形式打印出来，满足如下条件：



1. 数组行数等于二叉树高度。

2. 数组列数始终是奇数。

3. 根节点的值（以字符串表示）在第一行的正中间。根节点所在的行和列将剩余空间分成左下和右下两部分。将左子树打印在左下部分，右子树打印在右下部分，并且两部分所占空间相同。如果一个子树为空，但是另一个子树非空，不需要打印空的子树，但是需要预留出跟非空子树相同的空间。如果两个子树都为空，则不需要预留空间。

4. 没有用到的空间用 "" 表示。

5. 子树的打印也遵循同样的规则。



栗 1：

输入：
		
     1
    /
   2
   
输出：

[["", "1", ""],
 ["2", "", ""]]
 



栗 2：

输入：
     
     1
    / \
   2   3
    \
     4

输出：

[["", "", "", "1", "", "", ""],
 ["", "2", "", "", "", "3", ""],
 ["", "", "4", "", "", "", ""]]



栗 3：

输入：
	  
      1
     / \
    2   5
   / 
  3 
 / 
4 

输出：
[["",  "",  "", "",  "", "", "", "1", "",  "",  "",  "",  "", "", ""]
 ["",  "",  "", "2", "", "", "", "",  "",  "",  "",  "5", "", "", ""]
 ["",  "3", "", "",  "", "", "", "",  "",  "",  "",  "",  "", "", ""]
 ["4", "",  "", "",  "", "", "", "",  "",  "",  "",  "",  "", "", ""]]



注意：树的高度在 [1, 10] 之间。



想看英文原文的戳这里。

解题思路

我的解法



将我的解法与答案区的解法相比，顿时觉得自己思路“清奇”，竟然能想出这种旁门左道的方式。

规则解析



题目的描述很长，规则也不太容易理解。在磕磕绊绊之下，通过试验和分析 testcase 的正确答案与自己答案的区别后，终于悟出了其所要表达的含义。



主要来说下第 3/5 点规则，这么一大串描述看着都头大。简化如下：



• 根节点所在的列需要在数组的正中间。

• 左右子树所占的空间相等。即使有一个子树为空，也需占据空间。

• 每颗子树都要遵循相同的规则。也就是说，不仅仅针对于根节点，对于所有节点开始的子树，如出一辙。（这点很重要，不然栗子会看不懂）



最难理解的部分就是「左右子树所占的空间相等」。特别是当一个子树为空，另一个非空时。

等空间



由于左右子树空间相等，所以某棵子树所占的空间（也可理解为所占的列数），等于「其左右子树中较大的空间 * 2 + 1」，+1 是指它本身所占一列。这点应该比较好理解。



举几个栗子。



栗 1：



很明显，以 1 为根节点的树，所占空间为 3，因为左右子树都只有 1 个节点。



栗 2：



以 1 为根节点的树，所占空间为 7。为什么是 7 呢？



这需要分别计算出以 3 和 2 开始的子树所占的空间，取其大者。



• 以 3 开始的子树所占空间为 3。因为左子树 4 占 1 个空间，而左右子树需要有相同空间，因此总空间为 2*1+1=3。

• 以 2 开始的子树所占空间为 1。



因此，1 所占的空间为 2*3+1=7。



不清楚的可以看这张图，我将空间扩展的部分画了出来。





栗 3：

看个更复杂些的二叉树。





根节点 1 占据的空间是多少呢？你可以自己先想一下，答案是15。



我们逐个节点进行分析：

• 计算节点 1 的空间，需要计算出节点 3 和 2 的空间。

• 节点 2 的空间，肉眼可见为 1。

• 节点 3 的空间，需要计算出 4 和 5 的空间。

• 4 的空间为 1。

• 5 的空间，需要计算 6 的空间。

• 6 的空间为 1。

• 再逐步往上退，5 的空间为 2*1+1=3。

• 3 的空间，取 4/5 中最大的再做运算，为 2*3+1=7。

• 1 的空间，取 2/3 中最大的再做运算，为 2*7+1=15。



同样，下图是扩展后的空间。





从上述几个栗子中，我们可以总结出节点空间的计算方法。

// 父节点空间 = 左右子树空间最大值 * 2 + 1
f(node) = max(f(node.left), f(node.right)) * 2 + 1

思路



在了解等空间的概念后，下面来说说我自己的思路。



在二维矩阵中填入节点值，就得知道每个节点所在的行和列。行数很好求，因为在遍历过程中可知道当前层数，主要是列数的求法。



首先如果我们将整体的列数求出来，那么根节点的位置是知道的。更进一步，如果知道了子节点与父节点的相差列数，那么子节点的位置也可求出。所以我的主要思路就是利用子节点与父节点的相差列数来计算所有节点位置。



• 对于每个节点，其所占的空间是可以求出来的。

• 每个节点与其父节点的宽度距离，即相差的列数，也能求出。即其左右子树最大空间。

• 每层节点与其父节点的距离都是相同的，取各个节点计算出来的最大值。

• 最终算出根节点所占的总列数，则根节点的位置可以确定。

• 再次从根节点遍历二叉树，由于每层节点距父节点的宽度已算出，则左右子节点所在的位置也可知。

假设 distance 为下一层的距离宽度，col 为当前列。

• 左节点所在列：col - distance - 1。

• 右节点所在列：col + distance + 1。



由于代码有点长，就不贴出来了，感兴趣的同学可以点此查看。



更优解法



翻了翻评论区的解法，找到另外一种新的思路。



由于是等空间，那么最终就是一个满二叉树。其实从上面的扩展空间的图也可以看出。



其实数组的列数就等于总节点数，因为每个节点都占一列。而满二叉树的总节点数为 2^h-1，所以列数也为 2^h-1。



同时数组的行数，也就是树的高度，我们可以预先求出。在知道了数组的行数和列数之后，下面就好办了。



假设 l 为左边界列，r 为右边界列，那么父节点所在的列数为 m=(1+r)/2。

• 对于左节点，其右边界为 m-1，边界范围为 [l, m-1]；

• 对于右节点，其左边界为 m+1，边界范围为 [m+1, r]。



这样就可以逐个求出节点所在的位置。



具体实现可点此查看。