代码随想录day20

654.最大二叉树

给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：

• 二叉树的根是数组中的最大元素。
• 左子树是通过数组中最大值左边部分构造出的最大二叉树。
• 右子树是通过数组中最大值右边部分构造出的最大二叉树。

通过给定的数组构建最大二叉树，并且输出这个树的根节点。

????????构造树一般采用的是前序遍历，每次找数组的最大值，因为先构造中间节点，然后递归构造左子树和右子树。

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        // 构造根节点
        TreeNode* node=new TreeNode(0);
       
        // 找数组的最大值
        int maxval=0;
        int maxidx=0;
        for(int i=0;i<nums.size();++i){
            if(nums[i]>maxval){
                maxval=nums[i];
                maxidx=i;
            }
        }
        node->val=maxval;

        // 构造左子树
        if (maxidx>0) {
            vector<int> newVec(nums.begin(), nums.begin() + maxidx);
            node->left = constructMaximumBinaryTree(newVec);
        }

        // 构造右子树
        if (maxidx<(nums.size() - 1)) {
            vector<int> newVec(nums.begin() + maxidx + 1, nums.end());
            node->right = constructMaximumBinaryTree(newVec);
        }
        return node;
    }
};

? ? ? ? 由于每次都构造一个新数组，优化后，无需构造新数组，直接传入左右数组的下标。

class Solution {
public:
    TreeNode* travel(vector<int> &nums,int left,int right){
        //左右下标不能相等
        if(left>=right) return nullptr;
        //找最大值
        int maxidx=left;
        for(int i=left+1;i<right;++i){
            if(nums[i]>nums[maxidx]){
                maxidx=i;
            }
        }
        //构造根节点
        TreeNode* root=new TreeNode(nums[maxidx]);

        //构造左节点 左闭右开
        root->left=travel(nums,left,maxidx);

        //构造右节点
        root->right=travel(nums,maxidx+1,right);

        return root;
    }
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return travel(nums,0,nums.size());
    }
};

617.合并二叉树?? ? ? ??

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为?NULL 的节点将直接作为新二叉树的节点。

? ? ? ? ?使用先序遍历。

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(root1==nullptr){
            return root2;
        }
        if(root2==nullptr){
            return root1;
        }
        //先序遍历
        TreeNode* root=new TreeNode(root1->val+root2->val);
        root->left=mergeTrees(root1->left,root2->left);
        root->right=mergeTrees(root1->right,root2->right);
        return root;
    }
};

700.二叉搜索树中的搜索?

给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。

二叉搜索树是一个有序树：

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
• 它的左、右子树也分别为二叉搜索树

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if(root==nullptr||root->val==val) return root;
        TreeNode *res=nullptr;
        if(root->val>val) res=searchBST(root->left,val);
        if(root->val<val) res=searchBST(root->right,val);
        return res;
    }
};

98.验证二叉搜索树?

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

• 节点的左子树只包含小于当前节点的数。
• 节点的右子树只包含大于当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

要知道中序遍历下，输出的二叉搜索树节点的数值是有序序列。

有了这个特性，验证二叉搜索树，就相当于变成了判断一个序列是不是递增的了。

可以递归中序遍历将二叉搜索树转变成一个数组,后只要比较一下，这个数组是否是有序的，注意二叉搜索树中不能有重复元素

class Solution {
public:
    void isvaild(vector<int> &ans,TreeNode* root){
        if(root==nullptr) return;
        isvaild(ans,root->left);
        ans.push_back(root->val);
        isvaild(ans,root->right);
    }
    bool isValidBST(TreeNode* root) {
        vector<int> ans;
        isvaild(ans,root);
        for(int i=0;i<ans.size()-1;++i){
            if(ans[i]>=ans[i+1]) return false;
        }
        return true;
    }
};

?