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