输出二叉树

难度:

标签:

题目描述

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

树的高度为 height ，矩阵的行数 m 应该等于 height + 1 。
矩阵的列数 n 应该等于 2^height+1 - 1 。
根节点 需要放置在顶行的 正中间 ，对应位置为 res[0][(n-1)/2] 。
对于放置在矩阵中的每个节点，设对应位置为 res[r][c] ，将其左子节点放置在 res[r+1][c-2^height-r-1] ，右子节点放置在 res[r+1][c+2^height-r-1] 。
继续这一过程，直到树中的所有节点都妥善放置。
任意空单元格都应该包含空字符串 "" 。

返回构造得到的矩阵 res 。

示例 1：

输入：root = [1,2]
输出：
[["","1",""],
 ["2","",""]]

示例 2：

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

提示：

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

代码结果

运行时间: 28 ms, 内存: 15.9 MB

/*
 * 思路：
 * 1. 使用流操作来遍历树，计算高度并构造结果矩阵。
 * 2. 利用流的forEach和map方法来简化矩阵的填充操作。
 */
 
import java.util.stream.Collectors;
import java.util.stream.IntStream;
 
public class Solution {
    private int getHeight(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.max(getHeight(root.left), getHeight(root.right));
    }
 
    public List<List<String>> printTree(TreeNode root) {
        int height = getHeight(root);
        int m = height + 1;
        int n = (int) Math.pow(2, height + 1) - 1;
 
        // 初始化结果矩阵
        List<List<String>> res = IntStream.range(0, m)
            .mapToObj(i -> IntStream.range(0, n)
            .mapToObj(j -> "")
            .collect(Collectors.toList()))
            .collect(Collectors.toList());
 
        fill(res, root, 0, 0, n - 1);
        return res;
    }
 
    private void fill(List<List<String>> res, TreeNode root, int row, int left, int right) {
        if (root == null) return;
        int mid = (left + right) / 2;
        res.get(row).set(mid, Integer.toString(root.val));
        fill(res, root.left, row + 1, left, mid - 1);
        fill(res, root.right, row + 1, mid + 1, right);
    }
}

解释

方法:

这个题解使用深度优先搜索(DFS)的方式遍历二叉树。首先通过一次 DFS 求出树的高度 height。然后创建大小为 height * (2^height - 1) 的答案矩阵，所有元素初始化为空字符串。接着从根节点开始进行另一次 DFS，在答案矩阵中填入对应节点的值。填入位置根据当前节点的高度以及是左子节点还是右子节点来确定。最后返回填好的答案矩阵即可。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆

在计算左右子节点的位置时`c - diff`和`c + diff`，这里的diff是如何计算的，为什么是`2 ** (height - 2 - r)`?

▷

在计算左右子节点的位置时，`diff` 表示在填充答案矩阵中，子节点相对于父节点的水平偏移量。这个偏移量的计算方式`2 ** (height - 2 - r)`基于二叉树的层级结构和宽度。二叉树的每一层宽度大约是上一层的两倍，因此在第 `r` 层，从左到右的空间必须足够容纳所有可能的节点，即 `2 ** (height - r - 1)` 个潜在节点。而每个节点的左右子节点需要分别放在左半区和右半区的中心，故每个子节点与其父节点的距离为 `2 ** (height - r - 2)`。这里的 `-2` 是因为：要从这一层到下一层（减1），且下一层的宽度是这一层的一半（再减1）。

🦆

在确定二叉树的高度`height`时，为什么使用`height - 1`来初始化答案矩阵的行数，而不是直接使用`height`?

▷

实际上，题解中并没有使用 `height - 1` 来初始化答案矩阵的行数，而是直接使用 `height`。代码中的 `ans = [[''] * (2 ** height - 1) for _ in range(height)]` 表示使用树的高度 `height` 作为行数。每一层的树对应答案矩阵的一行，因此需要的行数正好是二叉树的高度。

🦆

如何保证在填充答案矩阵时，不会在同一位置重复填充节点值，特别是在具有多个子树分支的复杂结构中？

▷

在填充答案矩阵时，通过精确计算每个节点值应该填充的位置，可以避免重复填充。具体地，每个节点的位置是根据其在树中的深度（行）和偏移量（列）计算得到的。由于二叉树的性质，每个节点最多有两个子节点，且每个子节点的位置都是基于父节点的位置进行偏移的。这种偏移方式保证了在树的不同层和不同分支中，每个节点的位置是唯一的，因此不会有两个节点填充在同一个位置。

输出二叉树

题目描述

代码结果

解释

代码细节讲解

相关问题