深度剖析头条面试真题 | 二叉树那点事儿
0x01.一道面试题
看下这个题目描述(leetcode103题)：
给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
一图胜千言：
相信很多读者朋友都见过这道题目，没错 ，就是Z型变换遍历。
1.1 思考一下
依稀记得笔者当时面对这个题目栈和队列弄了一堆，答得也不是很好，现在想一想是陷入细节了，这样下去容易把自己绕晕。
现在从更宏观的角度去看就是层次遍历的一个变种问题，在遍历的过程中记住当前的层索引编号来确定从左到右还是从右到左，但是这道题一直没有动手做，今天想起来了就做一下吧！
在做这道题之前，昨天晚上做了两道 Easy 级别二叉树的题目，在脉脉上有些大神说做 easy 的题目还不如练练字，只能说大神就是大神呀，比不了比不了，反正Easy的我也做的不少，如人饮水冷暖自知，起跑线不一样，各自努力吧！
昨天做的两道题目分别是(笔者做的树的系列)：
LeetCode100题：
给定两个二叉树，编写一个函数来检验它们是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
LeetCode101题:
给定一个二叉树，检查它是否是镜像对称的。
只有题目做多了，我们才能从中提炼归纳，我们都知道二叉树问题大部分都是可以用递归来解决的，代码简洁到蒙圈，像我这种不太灵光的，还是倾向于用迭代来实现，当然最后还是会递归想一想，逃避不懂的知识点是不明智的。
1.2 一个插曲:我和立体几何
笔者总是喜欢天马行空，因为凡事都是相通的。
可能是因为空间思维能力弱(囧)，所以有的事情总会让我记忆犹新。
高二开始学习立体几何，具体的细节虽然记不清了，但是每次遇到题目就想起老师说的各种技巧各种辅助线，最终磕磕绊绊也能做出来，当然也有一些是完全没有思路的，所以从那个时候起我喜欢解析几何胜于立体几何。
考试之后老师会板书讲解，一听确实是那么回事，但是为啥当时就想不到呢？深深怀疑着自己的笨脑袋，但是也没办法，硬钢吧！
硬钢的路上并不轻松，即使做出来也花费很多时间，更多的是对此类问题的自信心逐渐减弱，这并不是个好现象，感受一下之前的题目：
没关系，请相信世界依然美好，上帝关上了窗的时候大概率给我们留着门呢。
果然让我找到了门，从我自己的角度去看，个人的解析计算能力是优于立体空间思维的，那为啥不能空间几何转换为数值计算呢？
原来有一种技术叫空间坐标系，这样就可以把空间几何的东西都坐标化，进而数值化，所以距离问题、面积问题、相交问题、平行问题等等都转换为了数值计算问题，深入学习了一段时间之后，自信心逐渐上来了，看到立体几何的题目不敢说庖丁解牛，最起码也看个大概，就这样立体几何再也没有成为我学习路上的拦路虎。
虽然这些事情已经过去很久了，但是解决立体几何问题的这种心理活动和现在做LeetCode上二叉树的问题很相似，一看题解貌似就是这么回事，一闭上题解，就不好下手(大囧)。
有时候，前进路上唯一的拦路虎，不是别人，就是我们自己，仅此而已。
0x02.寻找二叉树的门
不好意思前面又让大家喝了一碗鸡汤，现在准备开始啃鸡腿了呦！
前面提到我是最近两天做了3道二叉树的问题，发现了一些共性问题，所以才决定写一写的，或许后面做了更多的题目会有更多的心得，所以大家持续关注吧！
首先声明一点：笔者的迭代做法均不是最优解，基本上在AC的时候被一大半的人从时间和空间打败了，可能有人会问那你还写它干啥？
笔者看来最优解诚可贵，但是很多时候在没有见过题目，现场Coding时能有个正确的思路比啥都强，当时 ACM 大神就另当别论了，我们固然追求最优解，多种尝试解题，但是有个保底的通用思维也是双保险嘛，这也是本文的重点。
前面的三道题：两棵相同的树、一棵自成镜像对称的树、Z型遍历树，笔者除了用递归实现，最终都尝试了一种迭代层次遍历来解决，因为遍历对我们来说更加容易，紧张场景下我们必然选择自己熟悉的东西，来看下笔者在做这几道题是的一些过程：
-
100题 两棵相同的树问题
迭代层次遍历，保留树中的空节点，由于树节点的值是int，为了区分空节点，统一转换为string存储，这样一棵树经过转换就成为了vector
-
101题 一棵镜像的树
这个还是采用迭代层次遍历，int转string 保存空节点为null存储到vector
-
103题 锯齿状Z型遍历树
这个问题和镜像树有些类似，还是可以采用迭代分层遍历，由于涉及到按照层编号来修改遍历方向，因此需要做一些额外工作，对此笔者进行了一个AC实现，但是我并不觉得这个是我想要的通用方法，所以我并没有在遍历过程中判断层，因为在树上做其他操作容易让我晕，索性遍历存储为vector
从上面的三道题可以看到，我均使用了 迭代式层次遍历 ，区别在于根据每道题的特性做了 数组级别的调整 ，而不是 树级别的调整 ，我们知道数组更好理解也更好处理，这是个 降维过程 。
写到这里，仿佛有点意思了，所以 再次重申本文不是找最优解而是通用策略，目的是我们在面试场上迅速找个一个可靠的解决方法，先实现再优化和Offer 更搭哦。
0x03.单挑Z型变换遍历
Talk is Cheap,Show Me The Code!
3.1 Z型变换草稿
我们从我认为更难一些的第103题来体验一下这个二叉树的门，开始我们的分析过程：
从一般到特殊的思维
二叉树本身就是树的一种简单特例，不是吗？所以这个启发很重要。
我们掌握规律更多的是完全二叉树和满二叉树，所以我引入虚拟null节点让普通树变为规律树，其实引入虚拟节点这个套路在分布式一致性哈希的时候就用过，我们为何不尝试一下呢？
从树到数组的降维
仍旧以上图的完全二叉树为例进行迭代层次遍历并且将int转换为string且存储null节点，这样整个二叉树就成了这样：[3,9,20,7,15,15,7,7,null,19,null]。
在遍历过程中我们不好判断null之后是否还会有其他非空节点，因此额外增加一个变量记录迭代遍历时队列中的非null节点个数，当队列中没有非空节点时遍历就可以结束了，这样我们存储的二叉树是没有空洞的，这个很重要，后面代码可以看到。
数组的处理
经过上面几个过程，我们初步达到了目标，所以这个方案是行得通的，那么愉快地开始编码吧！
3.2 我的糙代码
前面说了，这个版本的代码肯定不是最优的，不过还是看下究竟有多粗糙和糟糕吧：
具体的代码实现(未优化版本)：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
//处理每个层的数据:将null清除 将string转换为int 根据层数进行翻转
bool revseit(vector<string> &vec, int curlevl, vector<int> &res){
//由于层数是从1开始编号 因此满足奇数层从左到右不翻转 偶数层翻转为从右向左
vector<string>::iterator iter = vec.begin();
for(;iter!=vec.end();iter++){
if(*iter=="null")
continue;
res.push_back(std::stoi(*iter));
}
if(curlevl%2==0)
std::reverse(res.begin(),res.end());
return true;
}
//开始处理由二叉树构造满二叉树生成的vector
bool dealit(vector<string> &vec, vector<vector<int> > &res){
//从顶向下按照满二叉树切割每层 每层结点数遵循 等比数列 1 2 4 8 .... 2^(k-1) k=1,2,3...
//满二叉树的总结点数量S=2^k-1 由此可以计算层数 也就是子vector的数量
int nodecnt = vec.size();
int levcnt = log(nodecnt+1)/log(2);
//这一步是判断完全二叉树的情况
bool notfull = false;
if(pow(2,levcnt)-1!=nodecnt){
notfull=true;
}
//我们从第1层开始向后分层切割
int curlevl = 1;
vector<string> tmpvec;
vector<int> tmpsubres;
while(curlevl<=levcnt+1){
//临时结构清空
tmpvec.clear();
tmpsubres.clear();
//计算本层之前的全部结点数量 作为本次切片的起点
int lastsum = pow(2,curlevl-1)-1;
//计算本层的节点数 作为切片时的偏移量
int gap = pow(2,curlevl-1);
if(curlevl==levcnt+1){
if(notfull)
gap = nodecnt-lastsum;
else
break;
}
tmpvec.assign(vec.begin()+lastsum,vec.begin()+lastsum+gap);
revseit(tmpvec,curlevl,tmpsubres);
if(tmpsubres.size()>0)
res.push_back(tmpsubres);
curlevl++;
}
return true;
}
//非递归层次遍历 注意空节点的处理
void travese(TreeNode *root, vector<string> &vec){
//相当于一个标记位 记录队列中非空节点数量
int oknodecnt = 0;
TreeNode *node = root;
queue<TreeNode*> q;
q.push(node);
oknodecnt++;
while(!q.empty()&&oknodecnt>0)
{
TreeNode *top = q.front();
if(top){
//向队列装载左结点
if(top->left){
q.push(top->left);
oknodecnt++;
}else
q.push(NULL);
//向队列装载右节点
if(top->right){
q.push(top->right);
oknodecnt++;
}else
q.push(NULL);
//队头节点任务完成 可以弹出并加入到vector中
q.pop();
oknodecnt--;
vec.push_back(std::to_string(top->val));
}else{
//当队头节点时NULL时 为了保证满二叉树的特性 向队列中增加两个NULL作为其虚拟孩子节点
q.pop();
q.push(NULL);
q.push(NULL);
vec.push_back("null");
}
}
}
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int> > res;
vector<string> vectree;
if(!root)
return res;
//层次遍历
travese(root,vectree);
//处理遍历后生成的vector
dealit(vectree,res);
return res;
}
};
其实笔者之所以这么绕地去实现一个问题，也是为了由一道题练更多的知识点，代码中的注释写的还算详细，感兴趣的可以用 web 版的页面查看，手机上阅读体验差点意思。
0x04.其他两道题目的糙代码
对于 LeetCode 第 100 题相同的树和 LeetCode 第 101 题镜像树，笔者均用相同的路子进行解决，可以看下具体的实现。
4.1 第100题相同的树
具体代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
//虽然该题目是easy 但是为了尽量多的练习 实用了非递归中序遍历(包含空节点)、vector、queue、迭代器的基本用法
void travese(TreeNode *root, vector<string> &vec)
{
//选择非递归层次遍历
TreeNode *node = root;
queue<TreeNode*> q;
q.push(node);
while(!q.empty())
{
TreeNode *top = q.front();
if(top){
//左结点
if(top->left)
q.push(top->left);
else
q.push(NULL);
//右节点
if(top->right)
q.push(top->right);
else
q.push(NULL);
q.pop();
vec.push_back(std::to_string(top->val));
}else{
q.pop();
vec.push_back("null");
}
}
}
//遍历vector对比
bool comp(vector<string> &vecp, vector<string> &vecq){
vector<string>::iterator iterp = vecp.begin();
vector<string>::iterator iterq = vecq.begin();
if(vecq.size()!=vecp.size())
return false;
for(;iterp!=vecp.end(),iterq!=vecq.end();iterp++,iterq++){
if(*iterp == *iterq)
continue;
else
return false;
}
return true;
}
bool isSameTree(TreeNode* p, TreeNode* q) {
if(!p&&!q)
return true;
if(!q||!p)
return false;
//两棵树都非空的前提下
vector<string> vecp;
vector<string> vecq;
travese(p,vecp);
travese(q,vecq);
return comp(vecp,vecq);
}
};
4.2 第101题镜像树
具体代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
//从左到右层次遍历
void travese(TreeNode *root, vector<string> &vec)
{
//选择非递归层次遍历
TreeNode *node = root;
queue<TreeNode*> q;
q.push(node);
while(!q.empty())
{
TreeNode *top = q.front();
if(top){
//左结点
if(top->left)
q.push(top->left);
else
q.push(NULL);
//右节点
if(top->right)
q.push(top->right);
else
q.push(NULL);
q.pop();
vec.push_back(std::to_string(top->val));
}else{
q.pop();
vec.push_back("null");
}
}
}
//从右到左层次遍历
void revtravese(TreeNode *root, vector<string> &vec)
{
//选择非递归层次遍历
TreeNode *node = root;
queue<TreeNode*> q;
q.push(node);
while(!q.empty())
{
TreeNode *top = q.front();
if(top){
//右结点
if(top->right)
q.push(top->right);
else
q.push(NULL);
//左节点
if(top->left)
q.push(top->left);
else
q.push(NULL);
q.pop();
vec.push_back(std::to_string(top->val));
}else{
q.pop();
vec.push_back("null");
}
}
}
bool isSymmetric(TreeNode* root) {
//空树或者只有根节点的树
if(!root||(root->left==NULL&&root->right==NULL))
return true;
//其他情况
vector<string> vecleft;
vector<string> vecright;
travese(root,vecleft);
revtravese(root,vecright);
return vecleft==vecright;
}
};0x05.笔者小结
写到这里基本上就到尾声了，简单总结一下：
本文通过 3 道二叉树的问题展开，目前是让我们获得一种在紧张场合快速切入解题的思路，其中涉及到一些自己的习惯可能并不为很多人接受，其次笔者本着一道题复习多个知识点的原则实现了很长的代码，无他就是为了练习。
做LeetCode就像现在手机厂商发布会上跑个分看看，亮一亮时间和空间碾压了多少人，漂亮简洁的算法确实让人惊艳，但是其背后凝结了无数的糙代码。
道阻且长 戒骄戒躁 扎好马步 我们也可以练就九阳神功！
END
●
●
算法技术文不易，点“在看”你懂得