C++数据结构与算法——二叉树的修改与构造

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，最大值索引为maxIndex
        TreeNode * 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;
    }
};