【代码随想录二刷】Day15-二叉树-C++

代码随想录二刷Day15

今日任务

层序遍历
226.翻转二叉树
101.对称二叉树
语言：C++

层序遍历

102.二叉树的层序遍历

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> res;if(root == NULL) return res;queue<TreeNode*> que;que.push(root);while(!que.empty()){vector<int> tmp;int n = que.size();for(int i = 0; i < n; i++){TreeNode* cur = que.front();que.pop();tmp.push_back(cur->val);if(cur->left) que.push(cur->left);if(cur->right) que.push(cur->right);}res.push_back(tmp);}return res;}
};

107.二叉树的层序遍历II

class Solution {
public:vector<vector<int>> levelOrderBottom(TreeNode* root) {vector<vector<int>> res;if(root == NULL) return res;queue<TreeNode*> que;que.push(root);while(!que.empty()){vector<int> tmp;int n = que.size();for(int i = 0; i < n; i++){TreeNode* cur = que.front();que.pop();tmp.push_back(cur->val);if(cur->left) que.push(cur->left);if(cur->right) que.push(cur->right);}res.push_back(tmp);}reverse(res.begin(), res.end());return res;}
};

199.二叉树的右视图

class Solution {
public:vector<int> rightSideView(TreeNode* root) {vector<int> res;if(root == NULL) return res;queue<TreeNode*> que;que.push(root);while(!que.empty()){int n = que.size();for(int i = 0; i < n; i++){TreeNode* cur = que.front();que.pop();if(i == n - 1) res.push_back(cur->val);if(cur->left) que.push(cur->left);if(cur->right) que.push(cur->right);}}return res;}
};

637.二叉树的层平均值

class Solution {
public:vector<double> averageOfLevels(TreeNode* root) {vector<double> res;if(root == NULL) return res;queue<TreeNode*> que;que.push(root);while(!que.empty()){int n = que.size();double sum = 0;for(int i = 0; i < n; i++){TreeNode* cur = que.front();que.pop();sum += cur->val;if(cur->left) que.push(cur->left);if(cur->right) que.push(cur->right);}res.push_back(sum / n);}return res;}
};

429.N叉树的层序遍历

class Solution {
public:vector<vector<int>> levelOrder(Node* root) {vector<vector<int>> res;if(root == NULL) return res;queue<Node*> que;que.push(root);while(!que.empty()){int n = que.size();vector<int> tmp;for(int i = 0; i < n; i++){Node* cur = que.front();que.pop();tmp.push_back(cur->val);vector<Node*> children = cur->children;for(int j = 0; j < children.size(); j++){que.push(children[j]);}}res.push_back(tmp);}return res;}
};

515.在每个树行中找最大值

class Solution {
public:vector<int> largestValues(TreeNode* root) {vector<int> res;if(root == NULL) return res;queue<TreeNode*> que;que.push(root);while(!que.empty()){int n = que.size();int max = INT_MIN;for(int i = 0; i < n; i++){TreeNode* cur = que.front();que.pop();max = max > cur->val ? max : cur->val;if(cur->left) que.push(cur->left);if(cur->right) que.push(cur->right);}res.push_back(max);}return res;}
};

116.填充每个节点的下一个右侧节点指针

class Solution {
public:Node* connect(Node* root) {if(root == NULL) return root;queue<Node*> que;que.push(root);while(!que.empty()){int n = que.size();Node* pre = que.front();Node* cur;que.pop();if(pre->left) que.push(pre->left);if(pre->right) que.push(pre->right);for(int i = 1; i < n; i++){cur = que.front();que.pop();pre->next = cur;pre = cur;if(pre->left) que.push(pre->left);if(pre->right) que.push(pre->right);}pre->next = NULL;}return root;}
};

117.填充每个节点的下一个右侧节点指针II
代码和上道题相同

226. 翻转二叉树

链接：https://leetcode.cn/problems/invert-binary-tree/
深度优先遍历-递归（前/后序遍历的递归）
递归三部曲：确定参数和返回值，确定终止条件，确定单层递归逻辑

class Solution {
public:TreeNode* invertTree(TreeNode* root) {if(root == NULL) return root;swap(root->left, root->right);invertTree(root->left);invertTree(root->right);return root;}
};

深度优先遍历-迭代（前/后序遍历的迭代）

class Solution {
public:TreeNode* invertTree(TreeNode* root) {if(root == NULL) return root;stack<TreeNode*> st;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;}
};

广度优先遍历-层序遍历

class Solution {
public:TreeNode* invertTree(TreeNode* root) {if(root == NULL) return root;queue<TreeNode*> que;que.push(root);while(!que.empty()){int n = que.size();for(int i = 0; i < n; i++){TreeNode* cur = que.front();que.pop();swap(cur->left, cur->right);if(cur->left) que.push(cur->left);if(cur->right) que.push(cur->right);}}return root;}
};

101. 对称二叉树

链接：https://leetcode.cn/problems/symmetric-tree/
递归

class Solution {
public:bool compare(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 outside = compare(left->left, right->right);bool inside = compare(left->right, right->left);return outside && inside;}bool isSymmetric(TreeNode* root) {if(root == NULL) return root;return compare(root->left, root->right);}
};

迭代

class Solution {
public:bool isSymmetric(TreeNode* root) {if(root == NULL) return root;queue<TreeNode*> que;que.push(root->left);que.push(root->right);while(!que.empty()){TreeNode* node1 = que.front();que.pop();TreeNode* node2 = que.front();que.pop();if(node1 == NULL && node2 != NULL) return false;else if(node1 != NULL && node2 == NULL) return false;else if(node1 != NULL && node2 != NULL && node1->val != node2->val) return false;else if(node1 == NULL && node2 == NULL) continue;que.push(node1->left);que.push(node2->right);que.push(node1->right);que.push(node2->left);}return true;}
};

100.相同的树
递归

class Solution {
public:bool compare(TreeNode* pNode, TreeNode* qNode){if(pNode == NULL && qNode == NULL) return true;else if(pNode == NULL || qNode == NULL) return false;else if(pNode->val != qNode->val) return false;bool left = compare(pNode->left, qNode->left);bool right = compare(pNode->right, qNode->right);return left && right;}bool isSameTree(TreeNode* p, TreeNode* q) {if(p == NULL && q == NULL) return true;else if(p == NULL || q == NULL) return false;return compare(p, q);}
};

迭代

class Solution {
public:bool isSameTree(TreeNode* p, TreeNode* q) {if(p == NULL && q == NULL) return true;else if(p == NULL || q == NULL) return false;queue<TreeNode*> que;que.push(p);que.push(q);while(!que.empty()){TreeNode* node1 = que.front();que.pop();TreeNode* node2 = que.front();que.pop();if(node1 == NULL && node2 == NULL) continue;else if(node1 == NULL || node2 == NULL) return false;else if(node1->val != node2->val) return false;que.push(node1->left);que.push(node2->left);que.push(node1->right);que.push(node2->right);}return true;}
};

572.另一个树的子树
递归

class Solution {
public:bool compare(TreeNode* root, TreeNode* subRoot){if(root == NULL && subRoot == NULL) return true;else if(root == NULL || subRoot == NULL) return false;else if(root->val != subRoot->val) return false;bool left = compare(root->left, subRoot->left);bool right = compare(root->right, subRoot->right);return left && right;}bool dfs(TreeNode* root, TreeNode* subRoot){if(root == NULL && subRoot != NULL) return false;return compare(root, subRoot) || dfs(root->left, subRoot) || dfs(root->right, subRoot);}bool isSubtree(TreeNode* root, TreeNode* subRoot) {return dfs(root, subRoot);}
};

迭代（效率不高）

class Solution {
public:bool isSubtree(TreeNode* root, TreeNode* subRoot) {queue<TreeNode*> que1;que1.push(root);while(!que1.empty()){int n = que1.size();for(int i = 0; i < n; i++){TreeNode* cur = que1.front();que1.pop();if(cur->left) que1.push(cur->left);if(cur->right) que1.push(cur->right);if(cur != NULL && cur->val == subRoot->val){queue<TreeNode*> que2;int flag = 0;que2.push(cur);que2.push(subRoot);while(!que2.empty()){TreeNode* node1 = que2.front();que2.pop();TreeNode* node2 = que2.front();que2.pop();if(node1 == NULL && node2 == NULL) continue;else if(node1 == NULL || node2 == NULL){flag = 1;break;}else if(node1->val != node2->val){flag = 1;break;}//cout << node1->val << " " << node2->val << " " << flag << endl;que2.push(node1->left);que2.push(node2->left);que2.push(node1->right);que2.push(node2->right);}if(flag == 0) return true;}}}return false;}
};