输出二叉树 图解题解

把一棵二叉树摆进一张 m×n 的字符串矩阵

给一棵二叉树的根 root，要把它画进一张 m 行 n 列的字符串矩阵。行数 m 是树高 height 加一，列数 n 是 2^(height+1) − 1，根写在顶行正中，每个节点的左右孩子落到下一行、往两侧偏开一段，空格填空串。题面 root=[1,2] 输出 [["","1",""],["2","",""]]，高 1、2 行 3 列。

矩阵开多大、每个数落哪一格，都得先算准

难点不在遍历，在两处定位。矩阵多大，取决于树往下长多深：树高多一层，行数多一行、列数翻倍再减一。节点落哪一列，取决于它在第几层、从父节点哪侧分下来。任一处算偏，数就摆错格甚至越界。

尺寸由树高定，每往下一层偏移就对半缩

先求树高 h，也就是从根到最远叶子要走的边数。约定空节点高度是 −1，只有一个节点的树高度恰好是 0。有了 h,m = h+1 行、n = 2^(h+1) − 1 列。安放靠一次 DFS，顺着一条枝走到底再回头。DFS 到每个节点，带着行号 r、列号 c，把值写进 res[r][c]，再把 c 减、加偏移量传给左右孩子。偏移量是 2^(h−r−1)，根在第 0 层最大，越往下每层对半缩，因为越深的节点能占的列区间越窄。

DFS 在每格写一个值，再把区间对半分给左右孩子

从根开始 dfs(root, 0, (n−1)/2)：根站顶行正中。到节点 res[r][c] 先填值，再算偏移 d = 2^(h−r−1)，左孩子去 res[r+1][c−d]、右孩子去 res[r+1][c+d]，各自站到下一行那半区间的正中。碰到空节点直接返回，那格保持空串。整条递归只在重复一个动作：站中点、把区间对半分往下带。

拿 root=[1,2,3,null,4] 亲手摆一遍

先量高。叶子 3、4 高度都是 0;节点 2 挂着 4，高度 1;根 1 取较大的加一得高度 2,h=2。尺寸定下：m = 2+1 = 3 行，n = 2^3 − 1 = 7 列。根列 = (7−1)/2 = 3，把 1 写进 res[0][3]。

根在第 0 层，偏移 d = 2^(2−0−1) = 2：左孩子 2 落到 res[1][3−2]=res[1][1]，右孩子 3 落到 res[1][5]。节点 2 在第 1 层，偏移缩成 d = 2^(2−1−1) = 1，它没有左孩子，右孩子 4 落到 res[2][2]。4 正落在 res[2][2]，与题面一致。

空节点高度、列数、偏移，三处约定别记混

空节点高度得记 −1 而不是 0——记成 0，树高虚高一层、行列一起多算。列数是 2^(h+1) − 1 而非 2^h，少写那一倍宽度，右边节点就越界或叠到一起。偏移量随层递减 2^(h−r−1)，写成固定值，深层节点全站错列。空格填的是空串，既非 null 也非空格。

矩阵有 h+1 行、2^(h+1) − 1 列，光建表填空串就是 O(m·n);DFS 每个节点只走一次，递归栈最深到树高 O(h)，被矩阵盖过，时间空间都是 O(m·n)。单节点是 1×1 矩阵，root=[1,2] 则是 2 行 3 列、根居中孩子落在半边角上。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:
        def height(root):
            if root is None:
                return -1
            return 1 + max(height(root.left), height(root.right))

        def dfs(root, r, c):
            if root is None:
                return
            ans[r][c] = str(root.val)
            dfs(root.left, r + 1, c - 2 ** (h - r - 1))
            dfs(root.right, r + 1, c + 2 ** (h - r - 1))

        h = height(root)
        m, n = h + 1, 2 ** (h + 1) - 1
        ans = [[""] * n for _ in range(m)]
        dfs(root, 0, (n - 1) // 2)
        return ans

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<string>> printTree(TreeNode* root) {
        int h = height(root);
        int m = h + 1, n = (1 << (h + 1)) - 1;
        vector<vector<string>> ans(m, vector<string>(n, ""));
        dfs(root, ans, h, 0, (n - 1) / 2);
        return ans;
    }

    void dfs(TreeNode* root, vector<vector<string>>& ans, int h, int r, int c) {
        if (!root) return;
        ans[r][c] = to_string(root->val);
        dfs(root->left, ans, h, r + 1, c - pow(2, h - r - 1));
        dfs(root->right, ans, h, r + 1, c + pow(2, h - r - 1));
    }

    int height(TreeNode* root) {
        if (!root) return -1;
        return 1 + max(height(root->left), height(root->right));
    }
};

Java

import java.util.*;
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public List<List<String>> printTree(TreeNode root) {
        int h = height(root);
        int m = h + 1, n = (1 << (h + 1)) - 1;
        String[][] res = new String[m][n];
        for (int i = 0; i < m; ++i) {
            Arrays.fill(res[i], "");
        }
        dfs(root, res, h, 0, (n - 1) / 2);
        List<List<String>> ans = new ArrayList<>();
        for (String[] t : res) {
            ans.add(Arrays.asList(t));
        }
        return ans;
    }

    private void dfs(TreeNode root, String[][] res, int h, int r, int c) {
        if (root == null) {
            return;
        }
        res[r][c] = String.valueOf(root.val);
        dfs(root.left, res, h, r + 1, c - (1 << (h - r - 1)));
        dfs(root.right, res, h, r + 1, c + (1 << (h - r - 1)));
    }

    private int height(TreeNode root) {
        if (root == null) {
            return -1;
        }
        return 1 + Math.max(height(root.left), height(root.right));
    }
}