题目描述

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

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

示例

示例1：

img

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

示例 2：

img

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

提示：

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

代码

c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/*
 * @lc app=leetcode.cn id=655 lang=cpp
 *
 * [655] 输出二叉树
 */

// @lc code=start
/**
 * 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:
    int height;
    vector<vector<string>> printTree(TreeNode* root) {
        dfsGetHeight(root, -1);
        int m = this->height + 1, n = getNumPow(this->height + 1) - 1;
        vector<vector<string>> res(m, vector<string>(n, ""));
        
        /* d */
        // vector<vector<string>> res(1, tmp);
        dfs(root, 0, (n-1)/2, height, res);

        return res;
    }
    
    void dfs(TreeNode* root, int r, int c, int height, vector<vector<string>> &res) {
        // if (!root || r < 0 || c < 0 || r >= m || c >= n) return ;
        if (!root) return ;
        res[r][c] = to_string(root->val);
        dfs(root->left, r + 1, c - getNumPow(height - r - 1), height, res);
        dfs(root->right, r + 1, c + getNumPow(height - r - 1), height, res);
    }
    
    /** 
     * get TreeNode height
     * @height: -1 from root to get height.
     */
    void dfsGetHeight(TreeNode* root, int height) {
        if (!root) {
            return ;
        }
        height += 1;
        this->height = height > this->height ? height : this->height;
        dfsGetHeight(root->left, height);
        dfsGetHeight(root->right, height);
        // queue<TreeNode*> que;
        // que.push(root);
        // tmp.push_back(to_string(root->val));
        // while (!que.empty()) {
        //     TreeNode* lt = que.front()->left;
        //     TreeNode* rt = que.front()->right;
        //     que.pop();
        //     if (lt) {
        //         tmp.push_back(to_string(lt->val));
        //         que.push(lt);
        //     } else {
        //         tmp.push_back("null");
        //     }
        //     if (rt) {
        //         tmp.push_back(to_string(rt->val));
        //         que.push(rt);
        //     } else {
        //         tmp.push_back("null");
        //     }
        // }
    }

    /** 
     * @return: return (2)pow(num)
     */
    int getNumPow(int num) {
        if (num == 0) return 1;
        if (num < 0) return 0;
        int res = 2;
        for (int i = num; i > 1; --i) {
            res *= 2;
        }
        return res;
    }
};
// @lc code=end

java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
import java.util.ArrayList;
import java.util.List;

/*
 * @lc app=leetcode.cn id=655 lang=java
 *
 * [655] 输出二叉树
 */

// @lc code=start
/**
 * 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 Solution {
    private int height;
    public List<List<String>> printTree(TreeNode root) {
        List<List<String>> res = new ArrayList<List<String>>();
        dfsGetHeight(root, -1);
        int m = height + 1, n = getNumPow(height + 1) - 1;
        for (int i = 0; i < m; ++i) {
            List<String> tmp = new ArrayList<String>();
            for (int j = 0; j < n; ++j) {
                tmp.add("");
            }
            res.add(tmp);
        }
        dfs(root, 0, (n - 1) / 2, res);
        return res;
    }

    public void dfsGetHeight(TreeNode root, int height) {
        if (root == null) return ;
        height += 1;
        this.height = height > this.height ? height : this.height;
        dfsGetHeight(root.left, height);
        dfsGetHeight(root.right, height);
    }

    public void dfs(TreeNode root, int r, int c, List<List<String>> list) {
        if (root == null) return ;
        list.get(r).set(c, Integer.toString(root.val));
        dfs(root.left, r + 1, c - getNumPow(this.height - r - 1), list);
        dfs(root.right, r + 1, c + getNumPow(this.height - r - 1), list);
    }

    public int getNumPow(int num) {
        if (num < 0) return 0;
        if (num == 0) return 1;
        int res = 2;
        for (int i = num; i > 1; --i) {
            res *= 2;
        }
        return res;
    }
}
// @lc code=end

python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#
# @lc app=leetcode.cn id=655 lang=python3
#
# [655] 输出二叉树
#

# @lc code=start
# 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

from typing import Optional


class Solution:
    # height = 0
    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:
        self.height = 0

        def dfsGetHeight(root: Optional[TreeNode], height: int):
            if not root:
                return 
            height += 1
            if height > self.height:
                self.height = height
            dfsGetHeight(root.left, height)
            dfsGetHeight(root.right, height)

        def getNumPow(num: int) -> int:
            res = 1
            for _ in range(num):
                res *= 2
            return res

        dfsGetHeight(root, -1)
        m, n = self.height + 1, getNumPow(self.height + 1) - 1
        self.res = [[''] * n for _ in range(m)]

        def dfs(root: Optional[TreeNode], r: int, c: int):
            if not root:
                return
            self.res[r][c] = str(root.val)
            dfs(root.left, r + 1, c - getNumPow(self.height \
                - r - 1))
            dfs(root.right, r + 1, c + getNumPow(self.height \
                - r - 1))
        dfs(root, 0, (n - 1) // 2)
        return self.res


# @lc code=end

题目来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/print-binary-tree