day 20二叉树（六）【day19休息】

day20
代码随想录
2023.12.18

1. 654最大二叉树
二叉树递归题做多了，看这道题就很顺手了，思路也很简单，根据给的数组数组找到最大值索引，之后将数组分为两个子数组，分别递归传入函数构造左右子树。这样递归就完成了，然后写终止条件，就是子数组为空或者1的时候。如果为空，直接返回空指针NULL，如果为1，那就将该值赋给节点就ok，这样就完成了！

/**
 * 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:
    int index(vector<int> nums){
        int max=0;
        int result=0;
        for(int i=0;i<nums.size();i++){
            if(nums[i]>max){
                result=i;
                max = nums[result];
            }
                
        }
        return result;
    }
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        if(nums.size()==0) return NULL;
        TreeNode*root = new TreeNode(0);
        if(nums.size()==1) root->val=nums[0];
        int inde = index(nums);
    
        root->val = nums[inde];
        vector<int> left_num;
        for(int i=0;i<inde;i++){
            
            left_num.push_back(nums[i]);
            
        }
        root->left = constructMaximumBinaryTree(left_num);
        if(inde<(nums.size()-1)){
            vector<int> right_num;
            for(int i=inde+1;i<nums.size();i++)
                right_num.push_back(nums[i]);
            root->right = constructMaximumBinaryTree(right_num);
        }
        
        
        return root;
        
    }
};

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

3. 700二叉搜索树中的搜索
这道题也是简单的递归，首先确定终止条件，找不到val，也就是递归到叶子节点的子树（NULL），此时返回NULL；其次就是找到，直接返回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* searchBST(TreeNode* root, int val) {
        if(root==NULL)
            return NULL;
        if(root->val==val)
            return root;
            TreeNode*result;
        if(root->val > val)
            result = searchBST(root->left, val);
        else if(root->val < val)
            result = searchBST(root->right, val);
        
        return result;
        
    }
};

4. 98验证二叉搜索树
很简单，中序遍历的结果是递增的就行

/**
 * 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:

    void traversal(TreeNode* root, vector<int>& vec) {
        if (root == NULL) return;
        traversal(root->left, vec);
        vec.push_back(root->val); 
        traversal(root->right, vec);
    }
    bool isValidBST(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        for (int i = 1; i < result.size(); i++) {
            if (result[i] <= result[i - 1]) return false;
        }
        return true;
    }
};