2021-11-08每日刷题打卡

力扣——二叉搜索树

98. 验证二叉搜索树和面试题 04.05. 合法二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

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

示例 1：

输入：root = [2,1,3]
输出：true

咋一看，好像每次只当前节点值要小于右节点并且大于左节点就行，但不光是这样，它是整个左子树上的值都要小于当前节点，右子树上的值都要大于当前节点，比如如果上面的左节点1连了一个右节点5，虽然满足了1节点的条件，但根节点2要小于5，所以不满足左子树上所有值小于当前节点的设定了。

所以我们每次递归遍历的时候，要顺便传入一个最大值和最小值，一开始最大值最小值都是NULL，随着递归的进行，对于左子树来说：最小值会变成当前节点左子树的值，最大值会变成当前节点的值；对于右子树来说：最小值会变成当前节点的值，最大值会变成当前节点右子树的值。这样当每次遍历时，判断这个节点的val值是否在最小值和最大值之间，如果不在就说明不是一个合格的搜索二叉树。

/**
 * 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 flag=true;
    bool isValidBST(TreeNode* root) {
        if(!root->left&&!root->right)return flag;
        dfs(root,NULL,NULL);
        return flag;
    }
    void dfs(TreeNode* root,TreeNode* max,TreeNode* min)
    {
        if(!flag||!root)return;
        
        if(max&&root->val >= max->val)flag=false;
        if(min&&root->val <= min->val)flag=false;

        if(root->left)dfs(root->left,root,min);
        if(root->right)dfs(root->right,max,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:
    vector<int>v;
    bool isValidBST(TreeNode* root) {
        if(!root->left&&!root->right)return true;
        dfs(root);
        int n=v.size();
        for(int i=0;i<n-1;i++)
        {
            if(v[i]>=v[i+1])
                return false;
        }
        return true;
    }
    void dfs(TreeNode* root)
    {
        if(!root)return;
        dfs(root->left);
        v.push_back(root->val);
        dfs(root->right);
    }
};

面试题 04.02. 最小高度树和108. 将有序数组转换为二叉搜索树

给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。

示例:
给定有序数组: [-10,-3,0,5,9],

一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

      0 
     /  
   -3   9 
   /   / 
 -10  5 

我们利用二叉搜索树的中序序列为递增区间的性质来求得二叉树，我们假定这个有序数组为二叉树的中序序列，既然我们想把一个绳子只折一次变成最短，那肯定是要从中间对折，所以我们取数组的中点值为根节点，然后把左右两边的数组分成两个数组，左边的构成左子树，右边的构成右子树，再从左边的数组里取中间值构建根节点的左节点，右边的数组里取中间值构建成根节点的右节点…………循环往复。最后当数组没有数字时，我们就得到了最短的二叉树，返回根节点即可。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        TreeNode*root;
        dfs(root,nums);
        return root;
    }
    void dfs(TreeNode*&root,vector<int>nums)
    {
        int n=nums.size();
        if(!n)return;
        int len=n/2;
        vector<int>v1;
        vector<int>v2;
        root=new TreeNode(nums[len]);
        for(int i=0;i<len;i++)
            v1.push_back(nums[i]);
        for(int i=len+1;i<n;i++)
            v2.push_back(nums[i]);
        
        dfs(root->left,v1);
        dfs(root->right,v2);
    }
};

109. 有序链表转换二叉搜索树

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定的有序链表： [-10, -3, 0, 5, 9],

一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

  0
 / 

-3 9
/ /
-10 5

和上一题的解法一样，只不过我们先遍历一遍链表把链表各节点的val值存入vector中，再用vector重复上一题的操作。

（当然，也可以一遍一遍二叉树一遍遍历链表，只要用快慢指针就可以求得链表的中间值了）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
/**
 * 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* sortedListToBST(ListNode* head) {
        TreeNode* root;
        if(!head)return NULL;
        vector<int>v;
        while(head!=NULL)
        {
            v.push_back(head->val);
            head=head->next;
        }
        dfs(root,v);
        return root;
    }
    void dfs(TreeNode*&root,vector<int>nums)
    {
        int n=nums.size();
        if(!n)return;
        int len=n/2;
        root=new TreeNode(nums[len]);
        vector<int>v1;
        vector<int>v2;
        for(int i=0;i<len;i++)
            v1.push_back(nums[i]);
        for(int i=len+1;i<n;i++)
            v2.push_back(nums[i]);
        dfs(root->left,v1);
        dfs(root->right,v2);
    }
};

99. 恢复二叉搜索树

给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。

进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？

示例 1：

输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 左孩子，因为 3 > 1 。交换 1 和 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:
    vector<int>v;
    void recoverTree(TreeNode* root) {
        dfs(root);
        int i=0;
        sort(v.begin(),v.end());
        dfs1(root,i);
    }
    void dfs(TreeNode*&root)
    {
        if(!root)return;
        dfs(root->left);
        v.push_back(root->val);
        dfs(root->right);
    }
    void dfs1(TreeNode*&root,int &i)
    {
        if(!root)return;
        dfs1(root->left,i);
        root->val=v[i++];
        dfs1(root->right,i);
    }
};

1008. 前序遍历构造二叉搜索树

返回与给定前序遍历 preorder 相匹配的二叉搜索树（binary search tree）的根结点。

(回想一下，二叉搜索树是二叉树的一种，其每个节点都满足以下规则，对于 node.left 的任何后代，值总 < node.val，而 node.right 的任何后代，值总 > node.val。此外，前序遍历首先显示节点 node 的值，然后遍历 node.left，接着遍历 node.right。）

题目保证，对于给定的测试用例，总能找到满足要求的二叉搜索树。

示例：

输入：[8,5,1,7,10,12]
输出：[8,5,10,1,7,null,12]

因为是前序遍历，所以我们知道序列的第一个值为根节点，然后就像我们之前知道的，左子树的所有值小于根节点，右子树的所有值大于根节点，那么我们可以遍历一遍序列，把所有小于第一个值的元素存入一个vector容器v1里，大于第一个值的元素存入另一个vector容器v2里。再利用这两个数组分别去构造左右子树（重复如上步骤），最后得到的就是原来的二叉树了。

/**
 * 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* bstFromPreorder(vector<int>& preorder) {
        TreeNode* root;
        dfs(root,preorder);
        return root;
    }
    void dfs(TreeNode*&root,vector<int>preorder)
    {
        if(!preorder.size())return;
        vector<int>v1;
        vector<int>v2;
        int num=preorder[0],n=preorder.size();
        for(int i=1;i<n;i++)
            if(preorder[i]<num)
                v1.push_back(preorder[i]);
            else
                v2.push_back(preorder[i]);
        root=new TreeNode(num);
        dfs(root->left,v1);
        dfs(root->right,v2);
    }
};