Medium

题目描述

给你一个二叉树的根节点 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^10] 内
  • -99 <= Node.val <= 99
  • 树的深度在范围 [1, 10] 内

解题思路

解题思路

这道题需要按照特定的格式将二叉树打印到二维矩阵中。关键是理解题目给出的放置规则。

核心思路：

  1. 计算矩阵尺寸：首先需要计算二叉树的高度，然后确定矩阵的行数 m = height + 1 和列数 n = 2^(height+1) - 1。

  2. 理解放置规则：

    • 根节点放在第一行的中间位置 (0, (n-1)/2)
    • 对于在位置 (r, c) 的节点，其左子节点位置为 (r+1, c-2^(height-r-1))，右子节点位置为 (r+1, c+2^(height-r-1))

  3. 实现方法：可以使用递归的深度优先搜索来遍历树并填充矩阵。递归函数需要传入当前节点、当前行、当前列以及当前层级信息。

算法步骤：

  1. 计算树的高度
  2. 初始化空矩阵
  3. 使用 DFS 递归填充矩阵，根据公式计算子节点位置
  4. 返回填充完成的矩阵

这种方法时间复杂度为 O(height × width)，空间复杂度也是 O(height × width)。

代码实现

class Solution {
public:
    vector<vector<string>> printTree(TreeNode* root) {
        int height = getHeight(root);
        int rows = height + 1;
        int cols = (1 << (height + 1)) - 1;  // 2^(height+1) - 1
        
        vector<vector<string>> res(rows, vector<string>(cols, ""));
        
        dfs(root, 0, (cols - 1) / 2, height, res);
        
        return res;
    }
    
private:
    int getHeight(TreeNode* root) {
        if (!root) return -1;
        return 1 + max(getHeight(root->left), getHeight(root->right));
    }
    
    void dfs(TreeNode* node, int row, int col, int height, vector<vector<string>>& res) {
        if (!node) return;
        
        res[row][col] = to_string(node->val);
        
        int offset = 1 << (height - row - 1);  // 2^(height-row-1)
        
        dfs(node->left, row + 1, col - offset, height, res);
        dfs(node->right, row + 1, col + offset, height, res);
    }
};

class Solution:
    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:
        def get_height(node):
            if not node:
                return -1
            return 1 + max(get_height(node.left), get_height(node.right))
        
        def dfs(node, row, col, height, res):
            if not node:
                return
            
            res[row][col] = str(node.val)
            
            offset = 2 ** (height - row - 1)
            
            dfs(node.left, row + 1, col - offset, height, res)
            dfs(node.right, row + 1, col + offset, height, res)
        
        height = get_height(root)
        rows = height + 1
        cols = (2 ** (height + 1)) - 1
        
        res = [["" for _ in range(cols)] for _ in range(rows)]
        
        dfs(root, 0, (cols - 1) // 2, height, res)
        
        return res

public class Solution {
    public IList<IList<string>> PrintTree(TreeNode root) {
        int height = GetHeight(root);
        int rows = height + 1;
        int cols = (1 << (height + 1)) - 1;
        
        var res = new List<IList<string>>();
        for (int i = 0; i < rows; i++) {
            var row = new List<string>();
            for (int j = 0; j < cols; j++) {
                row.Add("");
            }
            res.Add(row);
        }
        
        DFS(root, 0, (cols - 1) / 2, height, res);
        
        return res;
    }
    
    private int GetHeight(TreeNode root) {
        if (root == null) return -1;
        return 1 + Math.Max(GetHeight(root.left), GetHeight(root.right));
    }
    
    private void DFS(TreeNode node, int row, int col, int height, IList<IList<string>> res) {
        if (node == null) return;
        
        res[row][col] = node.val.ToString();
        
        int offset = 1 << (height - row - 1);
        
        DFS(node.left, row + 1, col - offset, height, res);
        DFS(node.right, row + 1, col + offset, height, res);
    }
}

var printTree = function(root) {
    const getHeight = (node) => {
        if (!node) return -1;
        return 1 + Math.max(getHeight(node.left), getHeight(node.right));
    };
    
    const dfs = (node, row, col, height, res) => {
        if (!node) return;
        
        res[row][col] = node.val.toString();
        
        const offset = Math.pow(2, height - row - 1);
        
        dfs(node.left, row + 1, col - offset, height, res);
        dfs(node.right, row + 1, col + offset, height, res);
    };
    
    const height = getHeight(root);
    const rows = height + 1;
    const cols = Math.pow(2, height + 1) - 1;
    
    const res = Array(rows).fill().map(() => Array(cols).fill(""));
    
    dfs(root, 0, Math.floor((cols - 1) / 2), height, res);
    
    return res;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(height × width) = O(height × 2^height)
空间复杂度O(height × width) = O(height × 2^height)