【树】655. 输出二叉树

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     vector<vector<string>> printTree(TreeNode* root) 
13     {
14         int height = getHeight(root);
15         int widths = (1 << height) - 1;
16 
17         vector<vector<string>> res(height, vector<string>(widths, ""));
18         fill(root, res, 0, 0, widths - 1);
19         return res;
20     }
21 
22 private:
23     int getHeight(TreeNode* root)
24     {
25         if (nullptr == root)
26         {
27             return 0;
28         }
29 
30         return max(getHeight(root->left), getHeight(root->right)) + 1;
31     }
32 
33     void fill(TreeNode* root, vector<vector<string>>& res, int height, int left, int right)
34     {
35         if (nullptr != root)
36         {
37             int mid = left + (right - left) / 2;
38 
39             res[height][mid] = std::to_string(root->val);
40 
41             fill(root->left, res, height + 1, left, mid - 1);
42             fill(root->right, res, height + 1, mid + 1, right);
43         }
44     }
45 };