102. 二叉树的层序遍历
题目链接：https://leetcode.cn/problems/binary-tree-level-order-traversal/
算法思想：
使用队列存储遍历的节点,用size标记每一层节点的格式。外层循环控制遍历的层数，内存循环控制新加入的节点。
102.二叉树的层序遍历
107.二叉树的层次遍历II
199.二叉树的右视图
637.二叉树的层平均值
429.N叉树的层序遍历
515.在每个树行中找最大值
116.填充每个节点的下一个右侧节点指针
117.填充每个节点的下一个右侧节点指针II
104.二叉树的最大深度
111.二叉树的最小深度
这些题目都可以用层次遍历解决
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> q;
if(root!=NULL)
q.push(root);
vector<vector<int>> res;
while(!q.empty())
{
int size = q.size();
vector<int> tmp;
while(size--)
{
TreeNode* cur = q.front();
q.pop();
tmp.push_back(cur->val);
if(cur->left)
q.push(cur->left);
if(cur->right)
q.push(cur->right);
}
res.push_back(tmp);
}
return res;
}
};
226. 翻转二叉树
题目链接
https://leetcode.cn/problems/invert-binary-tree/
使用二叉树的前序遍历解决
递归三部走：
确定返回值
确定终止条件
确定单层递归的逻辑
代码：
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
//使用前序遍历解决
if(root==NULL)
return root;
TreeNode* tmp = root->left;
root->left = root->right;
root->right = tmp;
invertTree(root->left);
invertTree(root->right);
return root;
}
};
101. 对称二叉树
题目链接：
https://leetcode.cn/problems/symmetric-tree/
算法思想：
首先弄清楚需要用什么遍历方法。
需要用后续遍历，因为判断当前节点是否对称，需要子节点比较完成才可以。
实际上是比较两棵二叉树。
再强调下递归三步走：
1.确定返回值类型和参数
2.确定终止条件
3.确认代码逻辑
class Solution {
public:
bool compare(TreeNode*left, TreeNode*right)
{
if(left==NULL&&right!=NULL ||left!=NULL&&right==NULL)
return false;
if(left==NULL&&right==NULL)
return true;
if(left->val!=right->val)
return false;
bool out_res = compare(left->left, right->right);
bool int_res = compare(left->right, right->left);
return out_res&&int_res;
}
bool isSymmetric(TreeNode* root) {
if(root==NULL)
return true;
bool res = compare(root->left, root->right);
return res;
}
};
