102.二叉树的层序遍历
1.迭代
思路
1.创建一个队列
2.确定每一层的节点个数，对每一层进行遍历，将结果输出。
实现
点击查看代码
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> que;
vector<vector<int>> result;
if(root == nullptr)return result;
que.push(root);
while(!que.empty()){
int size = que.size();
vector<int> vec;
for(int i = 0; i < size; i++){
TreeNode* cur = que.front();
que.pop();
vec.push_back(cur->val);
if(cur->left)que.push(cur->left);
if(cur->right)que.push(cur->right);
}
result.push_back(vec);
}
return result;
}
};
226.反转二叉树
1.层序遍历
思路
1.建立一个队列
2.确定每一层的节点个数
3.交换每一个节点的左右子节点，并将其加入队列
实现
点击查看代码
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
queue<TreeNode*> que;
if(root == nullptr) return nullptr;
que.push(root);
while(!que.empty()){
int size = que.size();
for(int i = 0; i < size; i++){
TreeNode* cur = que.front();
que.pop();
if(cur == nullptr)continue;//也可以通过判断if（cur->left）
TreeNode* temp = cur->left;
cur->left = cur->right;
cur->right = temp;
que.push(cur->left);
que.push(cur->right);
}
}
return root;
}
};
2.前序遍历（递归是一样的思路）
思路
1.建立栈
2.交换每一个节点的左右子节点
实现
点击查看代码
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
stack<TreeNode*> st;
if(root != nullptr)st.push(root);
while(!st.empty()){
TreeNode* cur = st.top();
st.pop();
swap(cur->left,cur->right);
if(cur->right) st.push(cur->right);
if(cur->left) st.push(cur->left);
}
return root;
}
};
3.中序遍历.（无法实现）
思路
使用中序遍历时，操作中节点时，会把左右节点互换，左节点的子节点被操作两次。
101.对称二叉树
1.容器
思路
1.创建vector数组
2.对两边同时进行访问和比较
3.在vector中继续插入左右子节点
实现
点击查看代码
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if(root == nullptr) return true;
vector<TreeNode*> vec;
vec.push_back(root->left);
vec.push_back(root->right);
while(!vec.empty()){
TreeNode* p1 = vec.front();
vec.erase(vec.begin());
TreeNode* p2 = vec.back();
vec.pop_back();
if(!p1 && !p2)continue;
if(!p1 || !p2 || p1->val != p2 -> val){
return false;
}
vec.insert(vec.begin(),p1->right);
vec.insert(vec.begin(),p1->left);
vec.push_back(p2->left);
vec.push_back(p2->right);
}
return true;
}
};
2.递归
思路
1.参数和返回值
2.终止条件（注意要先保证不是nullptr才可以调用数据left->val）
3.单次遍历逻辑
实现
点击查看代码
class Solution {
public:
bool compare(TreeNode* left,TreeNode* right){
if(left == nullptr && right != nullptr)return false;
else if(left != nullptr && right == nullptr)return false;
else if(left == nullptr && right == nullptr) return true;
else if(left->val != right->val)return false;
bool a = compare(left->left,right->right);
bool b = compare(left->right,right->left);
return a && b;
}
bool isSymmetric(TreeNode* root) {
if(root == nullptr)return true;
return compare(root->left, root->right);
}
};