代码随想录|Day 14

Day 14 新年将至

一、理论学习

BFS 的使用场景总结：层序遍历、最短路径问题(https://leetcode.cn/problems/binary-tree-level-order-traversal/solutions/244853/bfs-de-shi-yong-chang-jing-zong-jie-ceng-xu-bian-l/)

BFS 的应用一：层序遍历

BFS 的应用二：最短路径

如果要更贴向代码二叉树的层序遍历可以看下面这个图

102二叉树的层序遍历

二、刷题部分

102. 二叉树的层序遍历

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>>result;queue<TreeNode*>que;if(root!=nullptr) que.push(root);while(!que.empty()){int size=que.size();vector<int>res;while(size--){TreeNode* tmp=que.front();que.pop();res.push_back(tmp->val);if(tmp->left){que.push(tmp->left);}if(tmp->right){que.push(tmp->right);}}result.push_back(res);}return result;}
};

226. 翻转二叉树 - 力扣（LeetCode）

翻转二叉树

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* invertTree(TreeNode* root) {if(root==nullptr) return root;swap(root->left, root->right);  // 中invertTree(root->left);         // 左invertTree(root->right);        // 右return root;}
};

101. 对称二叉树 - 力扣（LeetCode）

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool com(TreeNode* left,TreeNode* right){//递归终止条件if (left == NULL && right != NULL) return false;else if (left != NULL && right == NULL) return false;else if (left == NULL && right == NULL) return true;else if (left->val != right->val) return false;//单层逻辑bool out=com(left->left,right->right);bool in=com(left->right,right->left);return in&&out;}bool isSymmetric(TreeNode* root) {return com(root->left,root->right);}
};