写在前面：
本题来自今日Leet Code的每日一题栏目，看到一个dalao的解法后产生了兴趣。故本文凭我的理解复现一下代码，并记录一点思考。
题号：655
难度：Medium
题目
给你一棵二叉树的根节点root ，请你构造一个下标从$0$开始、大小为 $m \times n$ 的字符串矩阵res ，用以表示树的 格式化布局 。构造此格式化布局矩阵需要遵循以下规则：
树的高度为height ，矩阵的行数m应该等于height + 1。
矩阵的列数n应该等于$2^{height+1}-1$。
根节点需要放置在顶行的正中间 ，对应位置为res[0][(n-1)/2]。
对于放置在矩阵中的每个节点，设对应位置为res[r][c]，将其左子节点放置在$res[r+1][c-2^{height-r-1}]$，右子节点放置在$res[r+1][c+2^{height-r-1}]$。
继续这一过程，直到树中的所有节点都妥善放置。
任意空单元格都应该包含空字符串 "" 。
返回构造得到的矩阵 res 。
示例 1：
输入：root = [1,2]
输出：
[["","1",""],
["2","",""]]示例 2：
输入：root = [1,2,3,null,4]
输出：
[["","","","1","","",""],
["","2","","","","3",""],
["","","4","","","",""]]提示：
- 树中节点数在范围 [1, 210] 内
- -99 <= Node.val <= 99
- 树的深度在范围 [1, 10] 内
思路
按dalao的解法，写两个辅助函数，一个maxDepth，计算树的高度；一个dfs，遍历树并赋值。
前者不必说。
后者需要的参数有：
- 根节点
root - 当前行
r - 当前列
c int值k，对应题目所述，左右子节点所在位置$res[r+1][c-2^{height-r-1}]$、$res[r+1][c+2^{height-r-1}]$中的公有部分$2^{height-r-1}$- 矩阵
res
代码
/**
* 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) {}
* };
*/
#include <vector>
#include <string>
#include <math.h>
using std::string;
using std::vector;
using std::to_string;
using std::max;
using std::pow;
//用除号和pow代替移位操作符后，程序执行效率没有明显变化
class Solution {
public:
vector<vector<string>> printTree(TreeNode* root) {
int m = maxDepth(root);
int n = (1 << m) - 1;
int k = 1 << (m - 1);
vector<vector<string>> res(m,vector<string>(n,""));
int r = 0;
int c = n >> 1; //此处用 (n - 1) >> 1 也是一样的
dfs(root,r,c,k,res);
return res;
}
void dfs(TreeNode* root,int r,int c,int k,vector<vector<string>> &res){
if(root==NULL) return;
k >>= 1;
res[r][c] = to_string(root->val);
dfs(root->left,r+1,c-k,k,res);
dfs(root->right,r+1,c+k,k,res);
}
int maxDepth(TreeNode* root){
if(root==NULL) return 0;
return 1 + max(maxDepth(root->left),maxDepth(root->right));
}
};说明
初看dalao代码的时候，我疑惑于<<和>>的作用，网上冲浪一番才知道，这两个操作符是移位运算符。
想起来前段时间看郑莉老师的课是讲过，是我疏忽。
在这段代码里，移位运算符被用来做“除以2”的操作，和代替pow函数计算2的幂。
有的人说这样的效率比直接除和调用pow函数要高。想想理论上确实是这样，毕竟函数调用也有开销。
但实际对比后没发现明显差异，可能是在小段代码里体现不出来吧。逼格确实很高
全文完
也该睡觉了
Comments NOTHING