算法练习-day18

二叉树

654. 最大二叉树

题意：给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

1. 创建一个根节点，其值为 nums 中的最大值。
2. 递归地在最大值 左边 的 子数组前缀上 构建左子树。
3. 递归地在最大值 右边 的 子数组后缀上 构建右子树。

返回 nums 构建的 最大二叉树 。

示例：

       思路：本题的大致思路和之前做过的中序遍历和后序遍历得出二叉树非常类似。本题，我们只需要找到一个数组的最大元素作为根节点即可，然后以最大元素作为分界点，分割出左右子树的数组元素，继续按照上述方式找到最大元素作为根节点循环进行，直到所有数组中的元素都被使用完即可

C++代码：

    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        if(0==nums.size())//当传入的数组为空时，表示该树为空树或者该节点到头了
        {
            return nullptr;
        }
        int maxsignal=0;//标记一棵树的根节点在数组中的位置
        for(int i=0;i<nums.size();i++)//找到该位置
        {
            if(nums[maxsignal]<nums[i])
            {
                maxsignal=i;
            }
        }
        TreeNode* root=new TreeNode(nums[maxsignal]);//变为节点
        vector<int> leftnums(nums.begin(),nums.begin()+maxsignal);//将左右子树分离
        vector<int> rightnums(nums.begin()+maxsignal+1,nums.end());
        root->left=constructMaximumBinaryTree(leftnums);
        root->right=constructMaximumBinaryTree(rightnums);
        return root;
    }

617. 合并二叉树

题意：给你两棵二叉树： root1 和 root2 。想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始

示例：

思路：本题可以将节点的结合分成四种思路：

1. 两节点都为空
2. 两节点都不为空
3. 左节点不为空，但是右节点为空
4. 左节点为空，但是右节点不为空

在分类书写时，两节点都为空的情况可以写到后面两种分类中；然后再进行结合，以root1作为基准树，在root1的基础上进行节点结合，先判断后两种情况，此时也会捎带对第一种情况进行排除，最后就是都不为空的情况，直接在root1值的基础上加上root2的值即可

C++代码：

    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(nullptr==root1)//总共有四种情况，我们可以分为三种：左为空，输出右节点
        {
            return root2;
        }
        if(nullptr==root2)//右为空，输出左节点
        {
            return root1;
        }
        root1->val+=root2->val;//都不为空，就加到左节点上
        root1->left=mergeTrees(root1->left,root2->left);//左右节点需要一起递归
        root1->right=mergeTrees(root1->right,root2->right);
        return root1;
    }

700. 二叉搜索树中的搜索

题意：给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

示例：

思路：本题我的思路大致是：由于是搜索二叉树，所以树的特点是：

1. 左边的值都比根节点小，右边的值都比根节点大
2. 所有左子树和右子树自身必须也是二叉搜索树

因此我们需要先比较根节点，当根节点大时，说明val大概率在左子树中，root向左子树移动；当根节点小时，说明val大概率在右子树，root向右子树移动；当根节点等于val时，返回root

C++代码：

    TreeNode* searchBST(TreeNode* root, int val) {
        if(nullptr==root)//当找到叶子节点还没找到val时，返回nullptr
        {
            return nullptr;
        }
        if(root!=nullptr&&root->val>val)//比较根节点，不断缩小范围
        {
            root=searchBST(root->left,val);
        }
        if(root!=nullptr&&root->val<val)
        {
            root=searchBST(root->right,val);
        }
        return root;
    }

98. 验证二叉搜索树

题意：给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。有效 二叉搜索树定义如下：

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

示例：

思路：本题有两种思路：1.数组法：根据BST的特点我们可以得出中序遍历的节点会形成一个递增的元素，因此我们用中序遍历将节点值记录在数组中，然后判断数组是否严格递增，若是，则该树为BST。2.递归法：利用中序遍历，我们要满足两个条件即可证明该树为BST：

1. 该树的遍历的前一个节点值都小于后一个值
2. 该树的左子树和右子树都是BST

因此我们使用中序遍历不断比较前一个节点和后一个节点的值满足第一个条件，然后在最后输出时，再次判断左右子树均是BST即可证明整棵树是BST

数组整理法代码：

    void TrueBST(TreeNode* root,vector<int>& arr)//中序遍历，并存储遍历的节点
    {
        if(nullptr==root)
        {
            return ;
        }
        TrueBST(root->left,arr);
        arr.push_back(root->val);
        TrueBST(root->right,arr);
    }
    bool isValidBST(TreeNode* root) {
        vector<int> arr;
        TrueBST(root,arr);//整理出二叉树中节点的中序遍历
        for(int i=0;i<arr.size()-1;i++)//数组必须满足严格递增的趋势才能为真
        {
            if(arr[i]>=arr[i+1])
            {
                return false;
            }
        }
        return true;
    }

递归法代码：

    long long cur=LONG_MIN;//这里需要注意，有个示例是INT_MIN，因此我们不能使用INT_MIN作为我们的起始值，因此要更小的LONG_MIN作为起始值
    bool isValidBST(TreeNode* root) {
        if(nullptr==root)
        {
            return true;
        }
        bool left=isValidBST(root->left);//从下往上判断只要有一个false，那该节点之上的所有树判断都是false
        if(cur<root->val)
        {
            cur=root->val;
        }
        else
        {
            return false;
        }
        bool right=isValidBST(root->right);
        return left&&right;//最后在判断根节点的左右子树都为搜索二叉树
    }