2021-11-08每日刷題打卡

力扣——二叉搜索樹

98. 驗證二叉搜索樹和面試題 04.05. 合法二叉搜索樹

給你一個二叉樹的根節點 root ，判斷其是否是一個有效的二叉搜索樹，

有效二叉搜索樹定義如下：

節點的左子樹只包含小于當前節點的數，
節點的右子樹只包含大于當前節點的數，
所有左子樹和右子樹自身必須也是二叉搜索樹，

示例 1：

tree1.jpg (302×182) (leetcode.com)

輸入：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]，它可以表示下面這個高度平衡二叉搜索樹：

我們利用二叉搜索樹的中序序列為遞增區間的性質來求得二叉樹，我們假定這個有序陣列為二叉樹的中序序列，既然我們想把一個繩子只折一次變成最短，那肯定是要從中間對折，所以我們取陣列的中點值為根節點，然后把左右兩邊的陣列分成兩個陣列，左邊的構成左子樹，右邊的構成右子樹，再從左邊的陣列里取中間值構建根節點的左節點，右邊的陣列里取中間值構建成根節點的右節點…………回圈往復，最后當陣列沒有數字時，我們就得到了最短的二叉樹，回傳根節點即可，

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

recover1.jpg (422×302) (leetcode.com)

輸入：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]

1266.png (590×386) (leetcode-cn.com)

因為是前序遍歷，所以我們知道序列的第一個值為根節點，然后就像我們之前知道的，左子樹的所有值小于根節點，右子樹的所有值大于根節點，那么我們可以遍歷一遍序列，把所有小于第一個值的元素存入一個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);
    }
};

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/353292.html

標籤：其他

上一篇：“二進制運算式的無效運算元”

下一篇：【演算法千題案例】每日LeetCode打卡——71.找不同