代码随想录算法训练营第23期day19| 654.最大二叉树、617.合并二叉树、700.二叉搜索树中的搜索、98.验证二叉搜索树

目录

一、（leetcode 654）最大二叉树

二、（leetcode 617）合并二叉树

三、（leetcode 700）二叉搜索树中的搜索

四、（leetcode 98）验证二叉搜索树

---

一、（leetcode 654）最大二叉树

力扣题目地址

状态：AC。

和昨天的中序+后/前序遍历序列构建二叉树思路类似，每次递归寻找数组中的最大值，根据最大值的索引来切分左右子序列进行递归生成，可以用索引下标来避免重复生成vector带来的开销

class Solution {
public:
    TreeNode* traversal(vector<int>& nums, int begin, int end){
        if(begin == end) { return nullptr; }
        int max_num = INT_MIN, max_index = begin;
 
        // 确定最大值的索引
        for(int i = begin; i < end; ++i){
            if(max_num < nums[i]){
                max_num = nums[i];
                max_index = i;
            }
        }
 
        TreeNode* node = new TreeNode(max_num);
 
        // 进行左右子数组划分
        int left_left = begin, left_right = max_index;
        int right_left = max_index + 1, right_right = end;
 
        node->left = traversal(nums, left_left, left_right);
        node->right = traversal(nums, right_left, right_right);
 
        return node;
    }
 
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return traversal(nums, 0, nums.size());
    }
};

二、（leetcode 617）合并二叉树

力扣题目链接

状态：AC。

使用的方法可以AC但是不够简洁，留待后续改进

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        //进行前序遍历，如果两棵树都为空则返回空节点
        if(root1 == nullptr && root2 == nullptr){
            return nullptr;
        }
        TreeNode* node = new TreeNode(0);
 
        if(root1 != nullptr && root2 != nullptr){
            node->val = root1->val + root2->val;
            node->left = mergeTrees(root1->left, root2->left);
            node->right = mergeTrees(root1->right, root2->right);
        }else if(root1){
            node->val = root1->val;
            node->left = mergeTrees(root1->left, nullptr);
            node->right = mergeTrees(root1->right, nullptr);
        }else{
            node->val = root2->val;
            node->left = mergeTrees(nullptr, root2->left);
            node->right = mergeTrees(nullptr, root2->right);
        }
 
        return node;  
    }
};

三、（leetcode 700）二叉搜索树中的搜索

力扣题目地址

状态：AC。

简单的前序遍历比较

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if(root == nullptr) return nullptr;
 
        //前序遍历
        if(root->val == val){
            return root;
        }else if(root->val < val){
            return searchBST(root->right, val);
        }else{
            return searchBST(root->left, val);
        }
        
        return nullptr;
    }
};

四、（leetcode 98）验证二叉搜索树

力扣题目链接

状态：思路错误，不能简单地比较根节点和左右子节点的大小。

这道题可以通过中序遍历的顺序判断值是不是递增来判断，注意除了上面的那个思路问题，在实现时用于比较的值maxVal需要使用long long来初始化，以防测试用例中有INT_MIN。

class Solution {
public:
    long long maxVal = LONG_MIN;
    bool isValidBST(TreeNode* root) {
        if(root == nullptr) return true;
 
        bool left = isValidBST(root->left);
 
        //中序遍历查看是否符合递增
        if(root->val > maxVal){
            maxVal = root->val;
        }else{
            return false;
        }
 
        bool right = isValidBST(root->right);
 
        return left && right;
    }
};