655. Print Binary Tree

素颜马尾好姑娘i 2024-04-07 12:13 63阅读 0赞

Given the `root` of a binary tree, construct a **0-indexed** `m x n` string matrix `res` that represents a **formatted layout** of the tree. The formatted layout matrix should be constructed using the following rules:

*  The **height** of the tree is `height` and the number of rows `m` should be equal to `height + 1`.
 *  The number of columns `n` should be equal to `2height+1 - 1`.
 *  Place the **root node** in the **middle** of the **top row** (more formally, at location `res[0][(n-1)/2]`).
 *  For each node that has been placed in the matrix at position `res[r][c]`, place its **left child** at `res[r+1][c-2height-r-1]` and its **right child** at `res[r+1][c+2height-r-1]`.
 *  Continue this process until all the nodes in the tree have been placed.
 *  Any empty cells should contain the empty string `""`.

Return *the constructed matrix* `res`.

**Example 1:**

![43404576600cfdcd66c81009477cc4e0.jpeg][]

Input: root = [1,2]
    Output: 
    [["","1",""],
     ["2","",""]]

**Example 2:**

![21c6d14c529ac8d469af79c4eba892c2.jpeg][]

Input: root = [1,2,3,null,4]
    Output: 
    [["","","","1","","",""],
     ["","2","","","","3",""],
     ["","","4","","","",""]]

**Constraints:**

*  The number of nodes in the tree is in the range `[1, 210]`.
 *  `-99 <= Node.val <= 99`
 *  The depth of the tree will be in the range `[1, 10]`.

题目：给定一棵二叉树，生成一个字符串数组

思路：先判断二叉树的深度，以此生成一个空的字符串数组。数组行数为二叉树的层数，列数为pow(2, height) -1。用队列来记录一个满二叉树，空着的地方用NULL表示。放到相应的位置。

代码：

/**
     * 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 getDepth(TreeNode* node, int level){
            if(!node) return level;
            int l = getDepth(node->left, level+1);
            int r = getDepth(node->right, level+1);
            return max(l, r);
        }
        vector<vector<string>> printTree(TreeNode* root) {
            int Depth = getDepth(root, -1), col = pow(2, Depth+1)-1;
            queue<TreeNode*> q;
            q.push(root);
            vector<vector<string>> res(Depth+1, vector<string>(col, ""));
            int level = 0;
            while(!q.empty() && level <= Depth){
                int dis = col / 2, pos = dis, size = (int)pow(2, level);
                for(int i = 0; i < size; i++){
                    TreeNode* node = q.front();
                    q.pop();
                    if(node){
                        res[level][pos] = to_string(node->val);
                        q.push(node->left);
                        q.push(node->right);
                    } else {
                        q.push(NULL);
                        q.push(NULL);
                    }
                    pos += dis * 2 + 2;
                }
                level ++;
                col = dis;
            }
            return res;
        }
    };

[43404576600cfdcd66c81009477cc4e0.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/532e080a18104e09aa6d9bf04906ce47.jpeg
[21c6d14c529ac8d469af79c4eba892c2.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/78dfe68673014eb6a8ed89c6982cc3e9.jpeg