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就像现在手机厂商发布会上跑个分看看，亮一亮时间和空间碾压了多少人，漂亮简洁的算法确实让人惊艳，但是其背后凝结了无数的糙代码。
道阻且长 戒骄戒躁 扎好马步 我们也可以练就九阳神功！
</div>