lc--655:输出二叉树

655. 输出二叉树 - 力扣（LeetCode）https://leetcode.cn/problems/print-binary-tree/

分析：(列数和行数都已经告知了，只需要求出height即可。) 

class Solution 
{
public:
    int calDepth(TreeNode* root) 
    {
        int h = 0;
        if (root->left) 
        {
            h = max(h, calDepth(root->left) + 1);
        }
        if (root->right) 
        {
            h = max(h, calDepth(root->right) + 1);
        }
        return h;
     }
 
    void dfs(vector>& res, TreeNode* root, int r, int c, const int& height) {
        res[r][c] = to_string(root->val);
        if (root->left) 
        {
            dfs(res, root->left, r + 1, c - (1 << (height - r - 1)), height);
        }
        if (root->right) 
        {
            dfs(res, root->right, r + 1, c + (1 << (height - r - 1)), height);
        }
    }
 
    vector> printTree(TreeNode* root)     
    {
        int height = calDepth(root);
        int m = height + 1;
        int n = (1 << (height + 1)) - 1;
        vector> res(m, vector(n, ""));
        dfs(res, root, 0, (n - 1) / 2, height);
        return res;
    }
};

 

class Solution 
{
public:
    int calDepth(TreeNode* root) 
    {
        int res = -1;
        queue q;
        q.push(root);
        while (!q.empty()) 
        {
            int len = q.size();
            res++;
            while (len) 
            {
                len--;
                auto t = q.front();
                q.pop();
                if (t->left) 
                {
                    q.push(t->left);
                }
                if (t->right) 
                {
                    q.push(t->right);
                }
            }
        }
        return res;
    }
 
    vector> printTree(TreeNode* root) 
    {
        int height = calDepth(root);
        int m = height + 1;
        int n = (1 << (height + 1)) - 1;
        vector> res(m, vector(n, ""));
        queueint, int>> q;
        q.push({root, 0, (n - 1) / 2});
        while (!q.empty()) 
        {
            auto t = q.front();
            q.pop();
            int r = get<1>(t), c = get<2>(t);
            res[r][c] = to_string(get<0>(t)->val);
            if (get<0>(t)->left) 
            {
                q.push({get<0>(t)->left, r + 1, c - (1 << (height - r - 1))});
            }
            if (get<0>(t)->right) 
            {
                q.push({get<0>(t)->right, r + 1, c + (1 << (height - r - 1))});
            }
        }
        return res;
    }
};

待手撕（。。。。）