101. 对称二叉树
- 101. 对称二叉树
- 思路:递归,对称即两个子树的左边和右边分别一样;一个子树是左中右遍历,另一个是右中左遍历;写的时候可以分三步,确定函数参数以及返回类型,确定终止条件,确定递归逻辑
- 时间和空间:O(n)
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)
class Solution {
public:TreeNode* invertTree(TreeNode* root) {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)
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;}
};
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)
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;}
};