# 面试热点|二叉树那点事儿(一)下

## 0​x04.其他两道题目的糙代码

### 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.笔者小结

            </div>

|
1月前

22 0
|
1月前

33 0
|
29天前
【一刷《剑指Offer》】面试题 23：从上往下打印二叉树
【一刷《剑指Offer》】面试题 23：从上往下打印二叉树
35 0
|
29天前
【一刷《剑指Offer》】面试题 19：二叉树的镜像
【一刷《剑指Offer》】面试题 19：二叉树的镜像
23 0
|
30天前
【一刷《剑指Offer》】面试题 6：重建二叉树
【一刷《剑指Offer》】面试题 6：重建二叉树
18 0
|
1月前
|

21 0
|
1月前
|

28 0
|
1月前
【面试小知识】带你深入了解二叉树的前中序遍历
【面试小知识】带你深入了解二叉树的前中序遍历
29 0
|
1月前
|

【Java程序员面试专栏 数据结构篇】五 高频面试算法题：二叉树
【Java程序员面试专栏 数据结构篇】五 高频面试算法题：二叉树
43 0
|
6月前
|

LeetCode | 二叉树高频面试算法题汇总【速来】-2
LeetCode | 二叉树高频面试算法题汇总【速来】
40 0