408算法题leetcode--第17天
101. 对称二叉树
- 101. 对称二叉树
- 思路：递归，对称即两个子树的左边和右边分别一样；一个子树是左中右遍历，另一个是右中左遍历；写的时候可以分三步，确定函数参数以及返回类型，确定终止条件，确定递归逻辑
- 时间和空间：O(n)
/**
* 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 check(TreeNode* lhs, TreeNode* rhs){
if(!lhs && !rhs) return true;
if(!lhs || !rhs) return false;
return lhs->val == rhs->val && check(lhs->left, rhs->right) && check(lhs->right, rhs->left);
}
bool isSymmetric(TreeNode* root) {
return check(root, root);
}
};
226. 翻转二叉树
- 226. 翻转二叉树
- 思路：如注释；其实就是树的后序遍历
- 时间和空间：O(n)
/**
* 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) {
// 翻转左边，翻转右边，当前节点的left和right互换
if(root == nullptr) return nullptr;
TreeNode* left = invertTree(root->left);
TreeNode* right = invertTree(root->right);
root->left = right;
root->right = left;
return root;
}
};
103. 二叉树的锯齿形层序遍历
- 103. 二叉树的锯齿形层序遍历
- 思路：入队和正常bfs相同，但是需要临时数组做翻转/用双端队列存储
- 时间和空间：O(n)
/**
* 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>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>>ret;
if(root == nullptr) return ret;
queue<TreeNode*>q;
q.push(root);
while(!q.empty()){
int size = q.size();
vector<int>temp_ret;
for(int i = 0; i < size; i++){
TreeNode* temp = q.front();
q.pop();
temp_ret.push_back(temp->val);
if(temp->left) q.push(temp->left);
if(temp->right) q.push(temp->right);
}
if(ret.size() % 2 == 1) reverse(temp_ret.begin(), temp_ret.end());
ret.push_back(temp_ret);
}
return ret;
}
};
- 双端存储的
/**
* 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>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>>ret;
if(root == nullptr) return ret;
queue<TreeNode*>q;
q.push(root);
int left_order = 1;
while(!q.empty()){
int size = q.size();
deque<int>dq;
for(int i = 0; i < size; i++){
TreeNode* temp = q.front();
q.pop();
if(left_order){
dq.push_back(temp->val);
} else {
dq.push_front(temp->val);
}
if(temp->left) q.push(temp->left);
if(temp->right) q.push(temp->right);
}
ret.emplace_back(vector<int>(dq.begin(), dq.end()));
left_order = !left_order;
}
return ret;
}
};
105. 从前序与中序遍历序列构造二叉树
- 105. 从前序与中序遍历序列构造二叉树
- 思路：前序找根节点，中序找到对应节点然后进行数组的分割，最后递归两边继续
- 时间和空间：O(n)
/**
* 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* buildTree(vector<int>& preorder, vector<int>& inorder) {
if(preorder.empty()) return nullptr;
// 前序找根节点
TreeNode* root = new TreeNode(preorder[0]);
if(preorder.size() == 1) return root;
// 中序找对应节点的位置
int id = 0, size = inorder.size();
for(; id < size; id++){
if(inorder[id] == root->val){
break;
}
}
// 分割两个数组
vector<int>left_in{inorder.begin(), inorder.begin() + id};
vector<int>right_in{inorder.begin() + id + 1, inorder.end()};
vector<int>left_pre{preorder.begin() + 1, preorder.begin() + id + 1};
vector<int>right_pre{preorder.begin() + id + 1, preorder.end()};
root->left = buildTree(left_pre, left_in);
root->right = buildTree(right_pre, right_in);
return root;
}
};
原文地址：https://blog.csdn.net/weixin_58073817/article/details/142601975
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！