0x02.寻找二叉树的门
不好意思前面又让大家喝了一碗鸡汤，现在准备开始啃鸡腿了呦！
前面提到我是最近两天做了3道二叉树的问题，发现了一些共性问题，所以才决定写一写的，或许后面做了更多的题目会有更多的心得，所以大家持续关注吧！
首先声明一点：笔者的迭代做法均不是最优解，基本上在AC的时候被一大半的人从时间和空间打败了，可能有人会问那你还写它干啥？
笔者看来最优解诚可贵，但是很多时候在没有见过题目，现场Coding时能有个正确的思路比啥都强，当时ACM大神就另当别论了，我们固然追求最优解，多种尝试解题，但是有个保底的通用思维也是双保险嘛，这也是本文的重点。
前面的三道题：两棵相同的树、一棵自成镜像对称的树、Z型遍历树，笔者除了用递归实现，最终都尝试了一种迭代层次遍历来解决，因为遍历对我们来说更加容易，紧张场景下我们必然选择自己熟悉的东西，来看下笔者在做这几道题是的一些过程：
- 100题 两棵相同的树问题
迭代层次遍历，保留树中的空节点，由于树节点的值是int，为了区分空节点，统一转换为string存储，这样一棵树经过转换就成为了vector类型，从而树的问题转换为了数组问题。
- 101题 一棵镜像的树
这个还是采用迭代层次遍历，int转string 保存空节点为null存储到vector中，本题是一棵树的问题，有两种路子:
a.层次遍历中每一层的节点时回文式的
b.层次遍历时先左后右存储一个vector 再从右到左存储一个vector 两次遍历 两个vector相等 表明树是镜像的
笔者使用b方法编码并AC，a方法因为涉及分层判定回文稍微复杂一些
- 103题 锯齿状Z型遍历树
这个问题和镜像树有些类似，还是可以采用迭代分层遍历，由于涉及到按照层编号来修改遍历方向，因此需要做一些额外工作，对此笔者进行了一个AC实现，但是我并不觉得这个是我想要的通用方法，所以我并没有在遍历过程中判断层，因为在树上做其他操作容易让我晕，索性遍历存储为vector，其实最开始是按照满二叉树进行存储的，在提交过程中发现并不是最优的，所以做了一些调整，但是时间和空间都不算很好。
从上面的三道题可以看到，我均使用了迭代式层次遍历，区别在于根据每道题的特性做了数组级别的调整，而不是树级别的调整，我们知道数组更好理解也更好处理，这是个降维过程。
写到这里，仿佛有点意思了，所以再次重申本文不是找最优解而是通用策略，目的是我们在面试场上迅速找个一个可靠的解决方法，先实现再优化和Offer更搭哦。
0x03.单挑Z型变换遍历
Talk is Cheap,Show Me The Code!
3.1 Z型变换草稿
我们从我认为更难一些的第103题来体验一下这个二叉树的门，开始我们的分析过程：
- 从一般到特殊的思维
现实世界中大部分东西都是一般存在的，但是我们在课堂上学习的很多东西都是特例化存在，比如线性代数里面的方阵、二次型、物理中也是如此，这么做的原因是特例的东西富含更多的规律，更容易掌握，说道这个让我想起一句话："山不过来，我们就过去"。
二叉树本身就是树的一种简单特例，不是吗？所以这个启发很重要。
我们掌握规律更多的是完全二叉树和满二叉树，所以我引入虚拟null节点让普通树变为规律树，其实引入虚拟节点这个套路在分布式一致性哈希的时候就用过，我们为何不尝试一下呢？
- 从树到数组的降维
引入虚拟节点之后，我们就拥有了一棵完全二叉树，当然有时候补齐之后我们拥有的是满二叉树，满二叉树的情况就是比如在上图的倒数第二层叶子节点7上随便甩出来一个节点，引入虚拟节点null之后就是满二叉树了，我们可以把满二叉树当做完全二叉树的特例即可。
仍旧以上图的完全二叉树为例进行迭代层次遍历并且将int转换为string且存储null节点，这样整个二叉树就成了这样：[3,9,20,7,15,15,7,7,null,19,null]。
在遍历过程中我们不好判断null之后是否还会有其他非空节点，因此额外增加一个变量记录迭代遍历时队列中的非null节点个数，当队列中没有非空节点时遍历就可以结束了，这样我们存储的二叉树是没有空洞的，这个很重要，后面代码可以看到。
- 数组的处理
我们知道完全二叉树/满二叉树的节点索引是存在内存联系的，由于我们填充了null所以我们就可以根据index关系来进行分层再反转了，从而避免在树的遍历过程中进行层次的记录，两件事情没有关联，处理起来更加清爽，看下：
经过上面几个过程，我们初步达到了目标，所以这个方案是行得通的，那么愉快地开始编码吧！
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版的页面查看，手机上阅读体验差点意思。
