LeetCode 655. 输出二叉树(层次遍历、递归)

输出二叉树
BFS
① 用宽搜求出树的高度，矩阵的列数为（$2^h-1$2h−1 ）
② 然后用层次遍历这棵树，首先记录下父节点的位置，然后在BFS将子节点入队的时候，注意将子节点的位置求出后推入queue<int> index

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
 
/*
    f[1] = 1;
    f[2] = 3;
    f[3] = 7;
    ……
    f[n] = 2^n-1;
*/

class Solution {
public: 
    vector<vector<string>> printTree(TreeNode* root) {
        int h = getHeight(root);
        vector<vector<string>> ans(h,vector<string>((1<<h)-1,""));

        //层次遍历
        queue<TreeNode*> q;
        queue<int> index;
        q.push(root);
        index.push((1<<(h-1))-1);
        int layer = 1;
        while(!q.empty()){
            int size = q.size();
            while(size--){
                TreeNode* r = q.front();
                int idx = index.front();
                q.pop();                
                index.pop();
                ans[layer-1][idx] = to_string(r->val);
                if(r->left){
                    q.push(r->left);
                    index.push(idx - (1<<(h-layer-1)));
                }
                if(r->right){
                    q.push(r->right);
                    index.push(idx+ (1<<(h-layer-1)));
                }
            }
            layer++;
        }
        return ans;
    }

    int getHeight(TreeNode *root){
        int height=0;
        if(!root){
            return 0;
        }
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            int size = q.size();
            while(size--){
                TreeNode* r = q.front();
                q.pop();
                if(r->left){
                    q.push(r->left);
                }
                if(r->right){
                    q.push(r->right);
                }
            }
            height++;
        }
        return height;
    }
};

递归版
其实二叉树的定义就是基于递归的，所以递归地填满矩阵更加自然。
注意，在递归时注意层次的累加。

class Solution {
public:
    vector<vector<string>> ans;
    vector<vector<string>> printTree(TreeNode* root) {
        int h = dfs(root);
        unsigned long n = (1<<h)-1;
        ans.resize(h,vector<string>{n,""} );
        fill(root,0,ans[0].size(),0);
        return ans;
    }
    void fill(TreeNode *root,int l,int r,int h){
        if(!root){
            return;
        }
        ans[h][(l+r)/2] = to_string(root->val) ;
        fill(root->left,l,(l+r)/2,h+1);     //左闭右开
        fill(root->right,(l+r)/2+1,r,h+1);  
    }
    int dfs(TreeNode *root){
        if(!root) {
            return 0;
        }
        return max(1+dfs(root->left),1+dfs(root->right));
    }
};