代码随想录二刷 Day 20

 LeetCode：654.最大二叉树

这个分割左闭右开一开始不理解，没用过vector的构造函数

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        TreeNode* node = new TreeNode(0);
        if (nums.size() == 1) {
            node->val = nums[0];
            return node; //这句话只会调用一次
        }
        int max_value = 0;
        int max_index = 0;
        for(int i = 0; i < nums.size(); i++) {
            if (nums[i] > max_value) {
                max_value = nums[i];
                max_index = i;
            }
        }
        node->val = max_value;
        if (max_index > 0) {
            vector<int> new_array1(nums.begin(), nums.begin() + max_index); //左闭右开
            node->left = constructMaximumBinaryTree(new_array1);
        }
 
        if (max_index < nums.size() -1) {
            vector<int> new_array2( nums.begin() + max_index +1, nums.end());
            node->right = constructMaximumBinaryTree(new_array2);
        }
        return node; //这句话会调用很多次，最后一次就是返回结果的时候
    }
};

class Solution {
public:
    TreeNode* sum(TreeNode* root1, TreeNode* root2){
        //if(root1 == NULL && root2 == NULL)
        //return NULL;
        if (root1 == NULL) return root2;
        if (root2 == NULL) return root1;
        TreeNode *root =new TreeNode(root1->val + root2->val);
        root->left = sum(root1->left, root2->left);
        root->right =sum(root1->right, root2->right);
 
        return root;
    }
 
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        return sum(root1, root2);
    }
};

递归法： 

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
       if (root == NULL || root->val == val) return root; //root == NULL 如果不写的话会报错，这是当递归到最后一层还没找到匹配的情况
       TreeNode* result = new TreeNode(0);
       if (root->val > val) result =  searchBST(root->left, val);
       if (root->val < val) result =  searchBST(root->right, val);
       return result;
    }
};

迭代法： 

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        while (root != NULL) {
            if (root->val > val) root = root->left;
            else if (root->val < val) root = root->right;
            else return root;
        }
        return NULL;
    }
};