【DFS, 二叉树】输出二叉树

题目

655. 输出二叉树

---

给你一棵二叉树的根节点 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] 内

解题

方法一：DFS

思路

这题的解题步骤在题目里已经给好了：先深搜拿到二叉树的高度，然后算出矩阵的行数(m)和列数(n)，最后再根据题目给出的步骤再次深搜把节点值填入矩阵对应位置即可。

代码

class Solution {
    List<List<String>> ans;
    int height;

    int getHeight(TreeNode node) {
        return node == null ? 
            0 : Math.max(getHeight(node.left), getHeight(node.right)) + 1;
    }

    void dfs(TreeNode node, int r, int c) {
        ans.get(r).set(c, String.valueOf(node.val));
        int tmp = 1 << height - r - 1;
        if (node.left != null) dfs(node.left, r + 1, c - tmp);
        if (node.right != null) dfs(node.right, r + 1, c + tmp);
    }

    public List<List<String>> printTree(TreeNode root) {
        int m = getHeight(root), n = (1 << m) - 1;
        ans = new ArrayList<>();
        for (int i = 0; i < m; ++i) {
            List<String> row = new ArrayList<>();
            for (int j = 0; j < n; ++j) row.add("");
            ans.add(row);
        }
        height = m - 1;
        dfs(root, 0, (n - 1) / 2);
        return ans;
    }
}

class Solution {
    vector<vector<string>> ans;
    int depth;

    int getHeight(TreeNode* node) {
        if (!node) return 0;
        return max(getHeight(node->left), getHeight(node->right)) + 1;
    }

    void dfs(TreeNode* node, int r, int c) {
        ans[r][c] = to_string(node->val);
        if (node->left) dfs(node->left, r + 1, c - pow(2, depth - r - 1));
        if (node->right) dfs(node->right, r + 1, c + pow(2, depth - r - 1));
    }

public:
    vector<vector<string>> printTree(TreeNode* root) {
        int m = getHeight(root);
        int n = pow(2, m) - 1;
        ans.resize(m, vector<string>(n));
        depth = m - 1;
        dfs(root, 0, (n - 1) / 2);
        return ans;
    }
};

---

也可以换一种方法算出每个节点应该在的位置：

节点所在矩阵的行数永远是该节点在整个二叉树中的深度(根节点从 0 开始)，而所在矩阵的列数是以该节点为根节点的子树的中点，比如说：

这个二叉树的高度为 3，矩阵的列数是 $2^3-1=7$，也就是说每一列都是 $[0,7)$ 的数组那么：

• 根节点 1 所在的行数为其深度 0，所在的列数为 $\lfloor(0+7) / 2\rfloor=3$，所以它在 $(0, 3)$。
  • 它的左子树占有的列是 $[0, 3)$，右子树占有的列是 $(3, 7)$。
  • 节点 2 所在的行数为其深度 1，所在的列数为 $\lfloor(0+3) / 2\rfloor=1$，所以它在 $(1, 1)$。
    • 它的左子树占有的列是 $[0, 1)$，右子树占有的列是 $(1, 3)$。
    • 节点 4 所在的行数为其深度 2，所在的列数为 $\lfloor(0+1) / 2\rfloor=0$，所以它在 $(2, 0)$。
    • 节点 5 所在的行数为其深度 2，所在的列数为 $\lfloor(1+3) / 2\rfloor=2$，所以它在 $(2, 2)$。
  • 节点 3 所在的行数为其深度 1，所在的列数为 $\lfloor(3+7) / 2\rfloor=5$，所以它在 $(1, 5)$。
    • 它的没有左子树，右子树占有的列是 $(5, 7)$。
    • 节点 6 所在的行数为其深度 2，所在的列数为 $\lfloor(5+7) / 2\rfloor=6$，所以它在 $(2, 6)$。

按上面算出来的位置填入下表：

r\c	0	1	2	3	4	5	6
0				①
1		②				③
2	④		⑤				⑥

符合题意，代码如下：

class Solution {
    vector<vector<string>> ans;

    int getHeight(TreeNode* node) {
        if (!node) return 0;
        return max(getHeight(node->left), getHeight(node->right)) + 1;
    }

    void dfs(TreeNode* node, int begin, int end, int level) {
        int mid = begin + end >> 1;
        ans[level][mid] = to_string(node->val);
        if (node->left) dfs(node->left, begin, mid, level + 1);
        if (node->right) dfs(node->right, mid, end, level + 1);
    }

public:
    vector<vector<string>> printTree(TreeNode* root) {
        int m = getHeight(root);
        int n = pow(2, m) - 1;
        ans.resize(m, vector<string>(n));
        dfs(root, 0, n, 0);
        return ans;
    }
};

class Solution {
    List<List<String>> ans;

    int getHeight(TreeNode node) {
        return node == null ? 
            0 : Math.max(getHeight(node.left), getHeight(node.right)) + 1;
    }

    void dfs(TreeNode node, int begin, int end, int depth) {
        int mid = begin + end >> 1;
        ans.get(depth).set(mid, String.valueOf(node.val));
        if (node.left != null) dfs(node.left, begin, mid, depth + 1);
        if (node.right != null) dfs(node.right, mid, end, depth + 1);
    }

    public List<List<String>> printTree(TreeNode root) {
        int m = getHeight(root), n = (1 << m) - 1;
        ans = new ArrayList<>();
        for (int i = 0; i < m; ++i) {
            List<String> row = new ArrayList<>();
            for (int j = 0; j < n; ++j) row.add("");
            ans.add(row);
        }
        dfs(root, 0, n, 0);
        return ans;
    }
}