C++第二阶段——数据结构和算法，之前学过一点点数据结构，当时是基于Python来学习的，现在基于C++查漏补缺，尤其是树的部分。这一部分计划一个月，主要利用代码随想录来学习，刷题使用力扣网站，不定时更新，欢迎关注！

一、226.翻转二叉树

/*** 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) {if(root==NULL) return root;// 交换左右结点swap(root->left,root->right);// 左结点if(root->left) invertTree(root->left);if(root->right) invertTree(root->right);return root;}
};

二、从中序与后序遍历序列构造二叉树

/*** 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* traversal(vector<int>& inorder, vector<int>& postorder) {// 中序  左中右// 后序  左右中if(postorder.size()==0) return NULL;// 根节点TreeNode * root = new TreeNode(postorder[postorder.size()-1]);// 找索引位置if(postorder.size()==1) return root;int index;for(index=0;index<inorder.size();index++){// 找到索引的位置if(inorder[index]==root->val){break;}}// 分割数组// 中左vector<int> inleft(inorder.begin(),inorder.begin()+index);// 中右vector<int> inright(inorder.begin()+1+index,inorder.end());// 后左vector<int> postleft(postorder.begin(),postorder.begin()+inleft.size());// 后右vector<int> postright(postorder.begin()+inleft.size(),postorder.end()-1);root->left = traversal(inleft,postleft);root->right = traversal(inright,postright);return root;}TreeNode * buildTree(vector<int>& inorder, vector<int>& postorder) {if (inorder.size() == 0 || postorder.size() == 0) return NULL;return traversal(inorder, postorder);}
};

三、105.从前序与中序遍历序列构造二叉树

/*** 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.size()==0) return NULL;// 获取根节点TreeNode * root = new TreeNode(preorder[0]);if(preorder.size()==1) return root;int index;for(index=0;index<inorder.size();index++){if(inorder[index] == root->val){break;}}// 中左vector<int> midleft(inorder.begin(),inorder.begin()+index);// 中右vector<int> midright(inorder.begin()+index+1,inorder.end());// 前左vector<int> preleft(preorder.begin()+1,preorder.begin()+1+midleft.size());vector<int> preoright(preorder.begin()+1+midleft.size(),preorder.end());root->left = buildTree(preleft,midleft);root->right = buildTree(preoright,midright);return root;}
};

四、654.最大二叉树

/*** 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* constructMaximumBinaryTree(vector<int>& nums) {// 找到最大值int maxN = INT_MIN;int maxIndex = 0;for(int i=0;i<nums.size();i++){if(nums[i]>maxN){maxIndex = i;maxN = nums[i];}}// 最大值为maxN，最大值索引为maxIndexTreeNode * root = new TreeNode(maxN);if(nums.size()==1){return root;}// 左子树if(maxIndex>0){vector<int> leftN(nums.begin(),nums.begin()+maxIndex);root->left = constructMaximumBinaryTree(leftN);} // 右子树if(maxIndex<nums.size()-1){vector<int> rightN(nums.begin()+maxIndex+1,nums.end());root->right = constructMaximumBinaryTree(rightN);} return root; }
};

五、617.合并二叉树

/*** 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* mergeTrees(TreeNode* root1, TreeNode* root2) {if(root1==NULL) return root2;if(root2==NULL) return root1;root1->val += root2->val;root1->left = mergeTrees(root1->left,root2->left);root1->right = mergeTrees(root1->right,root2->right);return root1;}
};