网龙沧州网站制作,制作网站主要包括哪些步骤,宁波网站营销推广策划方案,赣州网站优化公司101. 对称二叉树
101. 对称二叉树思路#xff1a;递归#xff0c;对称即两个子树的左边和右边分别一样#xff1b;一个子树是左中右遍历#xff0c;另一个是右中左遍历#xff1b;写的时候可以分三步#xff0c;确定函数参数以及返回类型#xff0c;确定终止条件#…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:vectorvectorint zigzagLevelOrder(TreeNode* root) {vectorvectorintret;if(root nullptr) return ret;queueTreeNode*q;q.push(root);while(!q.empty()){int size q.size();vectorinttemp_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:vectorvectorint zigzagLevelOrder(TreeNode* root) {vectorvectorintret;if(root nullptr) return ret;queueTreeNode*q;q.push(root);int left_order 1;while(!q.empty()){int size q.size();dequeintdq;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(vectorint(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(vectorint preorder, vectorint 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;}}// 分割两个数组vectorintleft_in{inorder.begin(), inorder.begin() id};vectorintright_in{inorder.begin() id 1, inorder.end()};vectorintleft_pre{preorder.begin() 1, preorder.begin() id 1};vectorintright_pre{preorder.begin() id 1, preorder.end()};root-left buildTree(left_pre, left_in);root-right buildTree(right_pre, right_in);return root;}
};
