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;}
};