输出二叉树 图解题解

这道题到底在问什么

输入

root=[1,2]

输出

[["","1",""],["2","",""]]　高 1,矩阵 2 行 3 列

输入

root=[1,2,3,null,4]

输出

4 落在 res[2][2]　高 2,矩阵 3 行 7 列

最优解：一步一步想明白

1. 3记住「占区间、站中点、左右对半分」这句口诀,下面每一帧都在套它。
2. 45 个节点这就是要画的树:根是 50,左孩子 30、右孩子 80;30 底下还挂着 10,80 底下挂着 90。一共 5 个节点,我们要把它们摆进矩阵。
3. 5h = 2先量树高。从根一路往下数最长的那条路,50 到 30 再到 10,走了两条边,所以树高 h 等于 2。约定空节点高度是 −1,这样叶子的高度刚好是 0。
4. 6m = 3 行, n = 7 列有了 h,矩阵尺寸就定了。行数 m 等于 h 加 1,也就是 3 行;列数 n 等于 2 的 (h+1) 次方再减 1,等于 2 的 3 次方减 1,也就是 7 列。接下来就在这张 3 行 7 列的网格上摆数。
5. 73 × 7 全空先把这张 3 行 7 列的矩阵全部填上空串,得到一张干净的网格。现在从根开始,做一次 DFS 把节点一个个放进去。
6. 8区间 [0, 6] → 中点 3轮到节点 50。它分到的列区间是 [0, 6](蓝色高亮这一段),中点等于 (0+6) 除以 2,也就是第 3 列。50 就站在这一格的正中间。
7. 9res[0][3] = 50把 50 写进 res[0][3],这一格点亮。它还有孩子,接着要把区间对半分给左右子树。
8. 10左半 [0, 2] | 右半 [4, 6]50 把自己的区间从中点劈开:左半段 [0, 2] 留给左孩子,右半段 [4, 6] 留给右孩子。两个孩子都掉到下一行,各自再去站自己那半段的中点。
9. 11区间 [0, 2] → 中点 1轮到节点 30。它分到的列区间是 [0, 2](蓝色高亮这一段),中点等于 (0+2) 除以 2,也就是第 1 列。30 就站在这一格的正中间。
10. 12res[1][1] = 30把 30 写进 res[1][1],这一格点亮。它还有孩子,接着要把区间对半分给左右子树。
11. 13左半 [0, 0] | 右半 [2, 2]30 把自己的区间从中点劈开:左半段 [0, 0] 留给左孩子,右半段 [2, 2] 留给右孩子。两个孩子都掉到下一行,各自再去站自己那半段的中点。
12. 14区间 [0, 0] → 中点 0轮到节点 10。它分到的列区间是 [0, 0](蓝色高亮这一段),中点等于 (0+0) 除以 2,也就是第 0 列。10 就站在这一格的正中间。
13. 15res[2][0] = 10把 10 写进 res[2][0],这一格点亮。它是叶子,没有孩子,这条分支到底了。
14. 16右半 [2, 2] 留空30 没有右孩子,右半段 [2, 2] 也就空着。可以看到这些空格正好对应树上缺失的子树位置。
15. 17区间 [4, 6] → 中点 5轮到节点 80。它分到的列区间是 [4, 6](蓝色高亮这一段),中点等于 (4+6) 除以 2,也就是第 5 列。80 就站在这一格的正中间。
16. 18res[1][5] = 80把 80 写进 res[1][5],这一格点亮。它还有孩子,接着要把区间对半分给左右子树。
17. 19左半 [4, 4] | 右半 [6, 6]80 把自己的区间从中点劈开:左半段 [4, 4] 留给左孩子,右半段 [6, 6] 留给右孩子。两个孩子都掉到下一行,各自再去站自己那半段的中点。
18. 20左半 [4, 4] 留空80 没有左孩子,所以左半段 [4, 4] 不放任何值,整段一直是空串。空的地方就是树里缺的那条枝。
19. 21区间 [6, 6] → 中点 6轮到节点 90。它分到的列区间是 [6, 6](蓝色高亮这一段),中点等于 (6+6) 除以 2,也就是第 6 列。90 就站在这一格的正中间。
20. 22res[2][6] = 90把 90 写进 res[2][6],这一格点亮。它是叶子,没有孩子,这条分支到底了。
21. 235 个节点全部就位五个节点全部放完。每个值都站在自己区间的正中央,空格保持空串。这张矩阵就是树的格式化布局,从上往下、左右对称地排开。
22. 24与答案逐格一致对照一下:第 0 行正中间是 50,第 1 行 30 和 80 对称地分在左右,第 2 行最外侧是 10 和 90。每一格都和正确答案对得上,DFS 区间取中点的办法奏效。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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

#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));
    }
};

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));
    }
}

复杂度

面试官可能追问