代码随想录训练营第二十天打卡|654.最大二叉树 617.合并二叉树 700.二叉搜索树中的搜索 98.验证二叉搜索树

654.最大二叉树

1.有了之前构造二叉树的经验，这道题就不难了。区别在于之前是根据前序或后序数组找到根节点，再根据根节点在中序遍历数组中的位置将数组划分为左右两部分依次进行递归。而本题是找到最大值在数组中的位置，根据最大值位置将数组划分为左右两部分再依次进行递归，是少数一次就AC的题目。

/**
 * 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 nums_max(vector<int>& nums){//求数组最大值函数
    int max=INT_MIN;
    for(int i=0;i<nums.size();i++){
        if(nums[i]>max)
        max=nums[i];
    }
    return max;
}
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        //递归终止条件
        if(nums.size()==0) return nullptr;
        //数组非空则创建根节点把最大值结点加入其中
        int Max=nums_max(nums);
        TreeNode* root=new TreeNode(Max);
        //根节点就是叶节点则直接返回结点
        if(nums.size()==1) return root;
        int i;//找到数组分割结点
        for(i=0;i<nums.size();i++){
            if(nums[i]==Max)
            break;
        }
        //按左闭右开原则根据最大值结点位置把数组分割成左右两部分
        vector<int> leftnums(nums.begin(),nums.begin()+i);
        vector<int> rightnums(nums.begin()+i+1,nums.end());
        //递归划分后的左右数组并将结果加入返回结点
        root->left=constructMaximumBinaryTree(leftnums);
        root->right=constructMaximumBinaryTree(rightnums);
        return root;
    }
};

617.合并二叉树

（其实不难，但第一次操作两个二叉树还是不容易想到的。为什么1空2不空或1不空2空不能创建一个新节点接收返回值？因为新节点只能接收当前合并结果，而不空的结点可能还有左右子树存在）

1.递归法的朴素写法（依次讨论两个结点的4种情况）

/**
 * 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&&!root2) return NULL;//1,2都空
        if(root1&&!root2) //1不空，2空
        return root1;
        if(!root1&&root2) //1空，2不空
        return root2;
        //1,2都不空
        TreeNode* root=new TreeNode(root1->val+root2->val);
        root->left=mergeTrees(root1->left,root2->left);
        root->right=mergeTrees(root1->right,root2->right);
        return root;
    }
};

2.递归的简洁写法（1,2都不空的时候用1接收合并值）

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

3.迭代法（用辅助队列实现，对两个二叉树的相同位置的不同情况分别处理）

/**
 * 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;
        queue<TreeNode*> que;
        que.push(root1);
        que.push(root2);
        while(!que.empty()){
            TreeNode* cur1=que.front(); que.pop();
            TreeNode* cur2=que.front(); que.pop();
            cur1->val+=cur2->val;
            if(cur1->left&&cur2->left){
                que.push(cur1->left);
                que.push(cur2->left);
            }
            if(cur1->right&&cur2->right){
                que.push(cur1->right);
                que.push(cur2->right);
            }
            if(!cur1->left&&cur2->left){//1不空2空默认不做修改（因为返回的是1）
                cur1->left=cur2->left;
            }
            if(!cur1->right&&cur2->right){
                cur1->right=cur2->right;
            }
        }
        return root1;
    }
};

700.二叉搜索树中的搜索

1.递归法（根据二叉搜索树的特点每次只需要递归搜索二叉树的一半子树）

/**
 * 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;
        if(root->val>val) return searchBST(root->left,val);
        if(root->val<val) return searchBST(root->right,val);
        return NULL;
    }
};

2.迭代法（根据二叉搜索树的特性，迭代最简单的一集）

/**
 * 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) {
        while(root){
            if(root->val>val) root=root->left;
            else if(root->val<val) root=root->right;
            else return root;
        }
        return NULL;
    }
};

98.验证二叉搜索树

没记错的话应该是2022年的408数据结构真题，当时没做出来，现在也没做出来……

1.递归法（初始化初值），要利用搜索二叉树的特性，只能采用中序遍历，因为二叉搜索树的中序遍历是非递减序列。

/**
 * 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://递归法
    long long maxVal = LONG_MIN; // 因为后台测试数据中有int最小值
    bool isValidBST(TreeNode* root) {
        if (root == NULL) return true;
        bool left = isValidBST(root->left);
        // 中序遍历，验证遍历的元素是不是从小到大
        if (maxVal < root->val) maxVal = root->val;
        else return false;
        bool right = isValidBST(root->right);
        return left && right;
    }
};

2.递归法但不初始化初值，而是选择用一个前置指针记录上一个结点，初始值置为NULL。这样可以有效防止初始值不符合测试用例要求，且在一些需要回溯的场景提供方便。

/**
 * 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* pre=NULL;
    bool isValidBST(TreeNode* root) {
        if(root==NULL) return true;
        bool left=isValidBST(root->left);
        if(pre&&pre->val>=root->val) return false;
        pre=root;
        bool right=isValidBST(root->right);
        return left&&right;
    }
};

3.迭代法（就是套上中序遍历的迭代模板，在合适的位置上加入判断逻辑）

/**
 * 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://迭代法(只能中序遍历)
    bool isValidBST(TreeNode* root) {
        if(root==nullptr) return true;
        stack<TreeNode*> st;
        TreeNode* cur=root;
        TreeNode* pre=nullptr;//记录前一个结点，不用设置初值
        while(cur||!st.empty()){
            if(cur){
                st.push(cur);
                cur=cur->left;
            }
            else{
                cur=st.top();
                st.pop();
                if(pre&&pre->val>=cur->val) return false;//判断逻辑
                else pre=cur;
                cur=cur->right;
            }
        }
        return true;
    }
};

今日总结：痛哭流涕了。