代码随想录day15 ● 层序遍历 10 ● 226.翻转二叉树 ● 101.对称二叉树 2

102. 二叉树的层序遍历

 1 class Solution {
 2 public:
 3     vector<vector<int>> levelOrder(TreeNode* root) {
 4         //创建一个队列用于存储每一层的结点
 5         queue<TreeNode*> que;
 6         if (root != nullptr) que.push(root);
 7         //创建一个二维数组用于存放遍历结果
 8         vector<vector<int>> result;
 9         while (!que.empty()){
10             //获取一层的结点数量
11             int size = que.size();
12             //用于存放一层的结点的值
13             vector<int> vec;
14             for (int i = 0; i < size; i++){
15                 //取队列中的第一个结点
16                 TreeNode* node = que.front();
17                 //弹出该节点
18                 que.pop();
19                 //将该节点的值存入vec
20                 vec.push_back(node->val);
21                 //将该结点下的两左右节点cun'chu
22                 if (node->left) que.push(node->left);
23                 if (node->right) que.push(node->right);
24             }
25             result.push_back(vec);
26         }
27         return result;
28     }
29 };

107. 二叉树的层序遍历 II

 1 class Solution {
 2 public:
 3     vector<vector<int>> levelOrderBottom(TreeNode* root) {
 4         queue<TreeNode*> que;
 5         if (root != NULL) que.push(root);
 6         vector<vector<int>> result;
 7         while (!que.empty()) {
 8             int size = que.size();
 9             vector<int> vec;
10             // 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
11             for (int i = 0; i < size; i++) {
12                 TreeNode* node = que.front();
13                 que.pop();
14                 vec.push_back(node->val);
15                 if (node->left) que.push(node->left);
16                 if (node->right) que.push(node->right);
17             }
18             result.push_back(vec);
19         }
20         reverse(result.begin(), result.end());
21         return result;
22     }
23 };

226. 翻转二叉树

 1 class Solution {
 2 public:
 3     TreeNode* invertTree(TreeNode* root) {
 4         //创建一个队用于存储每一层的结点
 5         queue<TreeNode*> que;
 6         if (root != nullptr) que.push(root);
 7         //当队列非空持续遍历
 8         while (!que.empty()){
 9             //获取每一层的结点数
10             int size = que.size();
11             //遍历每一层的每个节点
12             for (int i = 0; i < size; i++){
13                 //取第一个结点
14                 TreeNode* node = que.front();
15                 //处理完了第一个节点就弹出该节点
16                 que.pop();
17                 swap(node->left, node->right);
18                 if (node->left) que.push(node->left);
19                 if (node->right) que.push(node->right);
20             }
21         }
22         return root;
23     }
24 };

101. 对称二叉树

 1 class Solution {
 2 public:
 3     //核心在于判断左右两个字数能否翻转
 4     bool compare(TreeNode* left, TreeNode* right){
 5         //递归终止的条件
 6         if (left == nullptr && right != nullptr) return false;
 7         else if (left != nullptr && right == nullptr) return false;
 8         else if (left == nullptr && right == nullptr) return true;
 9         else if (left->val != right->val) return false;
10         bool outside = compare(left->left, right->right);
11         bool inside = compare(left->right, right->left);
12         return outside && inside;
13     }
14     bool isSymmetric(TreeNode* root) {
15         if (root == nullptr) return false;
16         return compare(root->left, root->right);
17     }
18 };