二叉树|102.二叉树层序遍历、226.翻转二叉树、101.对称二叉树
102.二叉树层序遍历
自己审题思路
使用队列来维护每一层的节点
看完代码随想录题解后的收获
层序遍历的递归法和延伸题目
代码：
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> que;
if (root != NULL) que.push(root);
vector<vector<int>> result;
while (!que.empty()) {
int size = que.size();
vector<int> vec;
// 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
vec.push_back(node->val);
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
result.push_back(vec);
}
return result;
}
};
代码（递归）
class Solution {
public:
void dfs(TreeNode* cur, vector<vector<int>>& vec, int depth) {
if (cur == nullptr) return;
if (vec.size() < depth) vec.push_back(vector<int>());
vec[depth - 1].push_back(cur->val);
dfs(cur->left, vec, depth + 1);
dfs(cur->right, vec, depth + 1);
}
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
dfs(root, ans, 1);
return ans;
}
};
递归法还是使用的
dfs，但是给每层加了一个depth标志（从1开始），每次遍历到depth层时，向二维数组的depth-1行（因为数组下标从0开始）加入元素。每当二维数组的大小（行数）小于depth时，表明遍历到了新的一行，添加一行（添加一个空数组进去）。
参考详解
226.翻转二叉树
自己审题思路
遍历过程中swap左右孩子
看完代码随想录题解后的收获
不能使用中序遍历实现翻转
代码：
class Solution {
public:
void dfs(TreeNode* cur) {
if (cur == nullptr) return;
swap(cur->left, cur->right);
dfs(cur->left);
dfs(cur->right);
}
TreeNode* invertTree(TreeNode* root) {
dfs(root);
return root;
}
};
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> que;
if (root != NULL) que.push(root);
while (!que.empty()) {
int size = que.size();
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
swap(node->left, node->right);
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
}
return root;
}
};
参考详解
101.对称二叉树
自己审题思路
判断左右子树是否对称可以使用递归思想
看完代码随想录题解后的收获
具体的实现思路（各种方案的实现思路-----dfs，bfs，递归）
代码：
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;
return compare(left->left, right->right) && compare(left->right, right->left);
}
bool isSymmetric(TreeNode* root) {
if (root == nullptr) return true;
return compare(root->left, root->right);
}
};
参考详解
今日感悟
树结构的操作常用到递归思想
