国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

Leetcode打卡——二叉搜索樹(共8題)

Olivia / 3474人閱讀

摘要:也就是說,有個節(jié)點的平衡二叉搜索樹,它的高度是。以搜索操作為例,如果二叉搜索樹的高度為,則時間復(fù)雜度為。二叉搜索樹的高度的確很重要。樹集合,中的或者中的,是由高度平衡的二叉搜索樹實現(xiàn)的。

二叉搜索樹(BST)是二叉樹的一種特殊表示形式,它滿足如下特性:

每個節(jié)點中的值必須大于(或等于)存儲在其左側(cè)子樹中的任何值。
每個節(jié)點中的值必須小于(或等于)存儲在其右子樹中的任何值。

1.Leetcode98. 驗證二叉搜索樹


法一:利用二叉樹的性質(zhì),根結(jié)點的值大于左子樹上的點,小于右子樹上的點

const long long MAX=2e31;const long long MIN=-MAX;class Solution {public:    bool isValidBST(TreeNode* root) {        bool ans=search(root,MIN,MAX);        return ans;    }    bool search(TreeNode *root,long long  l,long long r){        if(root==NULL)return true;        if(root->val<=l||root->val>=r){            return false;        }        return search(root->left,l,root->val)&&search(root->right,root->val,r);            }};

法二:二叉搜索樹中序遍歷的結(jié)果一定是單調(diào)遞增的

class Solution {public:    bool isValidBST(TreeNode* root) {        stack<TreeNode*>st;                TreeNode *cur=root;        long long num=-2*1e10;        while(cur||!st.empty()){            while(cur){                st.push(cur);                cur=cur->left;            }            cur=st.top();            st.pop();            if(num>=cur->val){                return false;            }            num=cur->val;            cur=cur->right;        }        return true;    }   };

2.Leetcode173. 二叉搜索樹迭代器

class BSTIterator {public:    TreeNode *cur;    stack<TreeNode*>st;    BSTIterator(TreeNode* root) {        cur=root;    }        int next() {       while(cur){           st.push(cur);           cur=cur->left;       }       cur=st.top();       st.pop();       int ans=cur->val;       cur=cur->right;       return ans;    }        bool hasNext() {      return cur||!st.empty();    }};

3.Leetcode700. 二叉搜索樹中的搜索

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

4.Leetcode701. 二叉搜索樹中的插入操作

class Solution {public:    TreeNode* insertIntoBST(TreeNode* root, int val) {          if(root==NULL){              root=new TreeNode(val);              return root;          }          if(root->val>val)root->left=insertIntoBST(root->left,val);          if(root->val<val)root->right=insertIntoBST(root->right,val);          return root;              }};

5.Leetcode450. 刪除二叉搜索樹中的節(jié)點


有許多不同的刪除節(jié)點的方法,為了使整體操作變化最小,用一個合適的子節(jié)點來替換要刪除的目標(biāo)節(jié)點。根據(jù)其子節(jié)點的個數(shù),我們需考慮以下三種情況:

  1. 如果目標(biāo)節(jié)點沒有子節(jié)點,我們可以直接移除該目標(biāo)節(jié)點。
  2. 如果目標(biāo)節(jié)只有一個子節(jié)點,我們可以用其子節(jié)點作為替換。
  3. 如果目標(biāo)節(jié)點有兩個子節(jié)點,我們需要用其中序 后繼節(jié)點或者前驅(qū)節(jié)點來替換,再刪除該目標(biāo)節(jié)點。
    要刪除的節(jié)點不是葉子節(jié)點且擁有右節(jié)點,則該節(jié)點可以由該節(jié)點的后繼節(jié)點進行替代,該后繼節(jié)點位于右子樹中較低的位置。然后可以從后繼節(jié)點的位置遞歸向下操作以刪除后繼節(jié)點。
    要刪除的節(jié)點不是葉子節(jié)點,且沒有右節(jié)點但是有左節(jié)點。這意味著它的后繼節(jié)點在它的上面,但是我們并不想返回。我們可以使用它的前驅(qū)節(jié)點進行替代,然后再遞歸的向下刪除前驅(qū)節(jié)點。


Successor 代表的是中序遍歷序列的下一個節(jié)點。即比當(dāng)前節(jié)點大的最小節(jié)點,簡稱后繼節(jié)點。 先取當(dāng)前節(jié)點的右節(jié)點,然后一直取該節(jié)點的左節(jié)點,直到左節(jié)點為空,則最后指向的節(jié)點為后繼節(jié)點。

TreeNode * successor(TreeNode *root){     root=root->right;     while(root->left){        root=root->left;     }     return root;}

Predecessor 代表的是中序遍歷序列的前一個節(jié)點。即比當(dāng)前節(jié)點小的最大節(jié)點,簡稱前驅(qū)節(jié)點。先取當(dāng)前節(jié)點的左節(jié)點,然后取該節(jié)點的右節(jié)點,直到右節(jié)點為空,則最后指向的節(jié)點為前驅(qū)節(jié)點。

TreeNode *predecessor(TreeNode *root){   root=root->left;   while(root->right){       root=root->right;   }   return root;}
class Solution {public:    TreeNode* deleteNode(TreeNode* root, int key){         if(root==NULL)return NULL;         if(root->val==key){             if(!root->left&&!root->right){                 return NULL;             }else if(root->right){                 TreeNode *node=new TreeNode(successor(root)->val);                 node->left=root->left;                 node->right=root->right;                 node->right=deleteNode(node->right,node->val);                 return node;             }else if(!root->right&&root->left){                 TreeNode *node=new TreeNode(precessor(root)->val);                 node->left=root->left;                 node->right=root->right;                 node->left=deleteNode(node->left,node->val);                 return node;             }         }         TreeNode *l=deleteNode(root->left,key);         TreeNode *r=deleteNode(root->right,key);         root->left=l;         root->right=r;         return root;    }    TreeNode *successor(TreeNode *root){        root=root->right;        while(root->left){            root=root->left;        }        return root;    }    TreeNode *precessor(TreeNode*root){        root=root->left;        while(root->right){            root=root->right;        }        return root;    }};

二叉搜索樹的有優(yōu)點是,即便在最壞的情況下,也允許你在O(h)的時間復(fù)雜度內(nèi)執(zhí)行所有的搜索、插入、刪除操作。

6.Leetcode235. 二叉搜索樹的最近公共祖先


法一:自底向上遞歸,適用于一般二叉樹

class Solution {public:    TreeNode *ans;    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {        if(root==NULL)return NULL;        search(root,p,q);        return ans;    }    bool search(TreeNode *root,TreeNode*p,TreeNode *q){        if(root==NULL)return false;        bool pr=search(root->left,p,q);        bool qr=search(root->right,p,q);        if(pr&&qr||(root==p||root==q)&&(pr||qr)){            ans=root;            return true;        }        return root==q||root==p||qr||pr;    }};

法二:
利用二叉搜索樹的性質(zhì),我們可以快速地找出樹中的某個節(jié)點以及從根節(jié)點到該節(jié)點的路徑
如果當(dāng)前節(jié)點的值大于 p 和 q 的值,說明 p 和 q 應(yīng)該在當(dāng)前節(jié)點的左子樹,因此將當(dāng)前節(jié)點移動到它的左子節(jié)點;

如果當(dāng)前節(jié)點的值小于 p 和 q 的值,說明 p 和 q 應(yīng)該在當(dāng)前節(jié)點的右子樹,因此將當(dāng)前節(jié)點移動到它的右子節(jié)點;

如果當(dāng)前節(jié)點的值不滿足上述兩條要求,那么說明當(dāng)前節(jié)點就是分岔點。此時,p 和 q 要么在當(dāng)前節(jié)點的不同的子樹中,要么其中一個就是當(dāng)前節(jié)點。

class Solution {public:        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {       if(root==NULL)return NULL;       TreeNode *ans=root;       while(ans){          if(ans->val>p->val&&ans->val>q->val){              ans=ans->left;          }else if(ans->val<p->val&&ans->val<q->val){              ans=ans->right;          }else{              break;          }       }       return ans;    }    };

高度平衡的二叉搜索樹
一個高度平衡的二叉搜索樹(平衡二叉搜索樹)是在插入和刪除任何節(jié)點之后,可以自動保持其高度最小。也就是說,有 N 個節(jié)點的平衡二叉搜索樹,它的高度是 logN 。并且,每個節(jié)點的兩個子樹的高度不會相差超過 1。
二叉樹及其相關(guān)操作, 包括搜索、插入、刪除。當(dāng)分析這些操作的時間復(fù)雜度時,我們需要注意的是樹的高度是十分重要的考量因素。以搜索操作為例,如果二叉搜索樹的高度為 h ,則時間復(fù)雜度為 O(h) 。二叉搜索樹的高度的確很重要。
所以,我們來討論一下樹的節(jié)點總數(shù) N 和高度 h 之間的關(guān)系。對于一個平衡二叉搜索樹, 我們已經(jīng)在前文中提過,

但一個普通的二叉搜索樹,在最壞的情況下,它可以退化成一個鏈。

因此,具有 N 個節(jié)點的二叉搜索樹的高度在 logN 到 N 區(qū)間變化。也就是說,搜索操作的時間復(fù)雜度可以從 logN 變化到 N 。這是一個巨大的性能差異。
所以說,高度平衡的二叉搜索樹對提高性能起著重要作用。

高度平衡的二叉搜索樹在實際中被廣泛使用,因為它可以在 O(logN) 時間復(fù)雜度內(nèi)執(zhí)行所有搜索、插入和刪除操作。
常見的的高度平衡二叉樹:
紅黑樹
AVL樹
伸展樹
樹堆
平衡二叉搜索樹的概念經(jīng)常運用在 Set 和 Map 中。Set 和 Map 的原理相似。
通常,有兩種最廣泛使用的集合**:散列集合(Hash Set)和 樹集合(Tree Set)**。

樹集合,Java 中的 Treeset 或者 C++ 中的 set ,是由高度平衡的二叉搜索樹實現(xiàn)的。因此,搜索、插入和刪除的時間復(fù)雜度都是 O(logN) 。

散列集合,Java 中的 HashSet 或者 C++ 中的 unordered_set ,是由哈希實現(xiàn)的,但是平衡二叉搜索樹也起到了至關(guān)重要的作用。當(dāng)存在具有相同哈希鍵的元素過多時,將花費 O(N) 時間復(fù)雜度來查找特定元素,其中N是具有相同哈希鍵的元素的數(shù)量。 通常情況下,使用高度平衡的二叉搜索樹將把時間復(fù)雜度從 O(N) 改善到 O(logN) 。

哈希集和樹集之間的本質(zhì)區(qū)別在于樹集中的鍵是有序的。

7.110. 平衡二叉樹

class Solution {public:    bool ans=true;    bool isBalanced(TreeNode* root) {        if(root==NULL)return ans;        search(root);        return ans;    }    int search(TreeNode *root){        if(root==NULL)return 0;        int l=search(root->left);        int r=search(root->right);        if(abs(l-r)>1){            ans=false;            return -1;        }        return l>r?l+1:r+1;    }};

8.Leetcode108. 將有序數(shù)組轉(zhuǎn)換為二叉搜索樹

class Solution {public:    TreeNode* sortedArrayToBST(vector<int>& nums) {        return helper(nums, 0, nums.size() - 1);    }    TreeNode* helper(vector<int>& nums, int left, int right) {        if (left > right) {            return nullptr;        }        // 總是選擇中間位置左邊的數(shù)字作為根節(jié)點        int mid = (left + right) / 2;        TreeNode* root = new TreeNode(nums[mid]);        root->left = helper(nums, left, mid - 1);        root->right = helper(nums, mid + 1, right);        return root;    }};

文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/123351.html

相關(guān)文章

  • ?算法入門?《二叉 - 二叉搜索》簡單05 —— LeetCode 897. 遞增順序搜索

    文章目錄 一、題目1、題目描述2、基礎(chǔ)框架3、原題鏈接 二、解題報告1、思路分析2、時間復(fù)雜度3、代碼詳解 三、本題小知識四、加群須知 一、題目 1、題目描述 ??給你一棵二叉搜索樹,請按 中序遍歷 將其重新排列為一棵遞增順序搜索樹,使樹中最左邊的節(jié)點成為樹的根節(jié)點,并且每個節(jié)點沒有左子節(jié)點,只有一個右子節(jié)點。??樣例輸入: [5,3,6,2,4,null,8,1,null,null,nu...

    Soarkey 評論0 收藏0
  • LeetCode 之 JavaScript 解答第98 —— 驗證二叉搜索

    摘要:小鹿題目驗證二叉搜索樹給定一個二叉樹,判斷其是否是一個有效的二叉搜索樹。假設(shè)一個二叉搜索樹具有如下特征節(jié)點的左子樹只包含小于當(dāng)前節(jié)點的數(shù)。所有左子樹和右子樹自身必須也是二叉搜索樹。算法思路定義全局的變量,用來返回是否為二叉搜索樹。 Time:2019/4/24Title: Vaildata Binary Search TreeDifficulty: MediumAuthor: 小鹿 ...

    用戶84 評論0 收藏0
  • LeetCode 之 JavaScript 解答第112 —— 路徑總和(Path Sum)

    摘要:小鹿題目路徑總和給定一個二叉樹和一個目標(biāo)和,判斷該樹中是否存在根節(jié)點到葉子節(jié)點的路徑,這條路徑上所有節(jié)點值相加等于目標(biāo)和。說明葉子節(jié)點是指沒有子節(jié)點的節(jié)點。 Time:2019/4/26Title: Path SumDifficulty: EasyAuthor: 小鹿 題目:Path Sum(路徑總和) Given a binary tree and a sum, determin...

    lylwyy2016 評論0 收藏0
  • 【手把手帶你刷LeetCode】——11.二叉搜索的范圍和(DFS)

    摘要:大家簡單看一下純遞歸的解法原題二叉搜索樹的范圍和解法題目描述給定二叉搜索樹的根結(jié)點,返回值位于范圍之間的所有結(jié)點的值的和。 【前言】 今天是力扣打卡第11天! 感謝鐵汁們的陪伴,一起加油鴨!! 在第9天的時候?qū)戇^這道題的遞歸解題方法,其實DFS使用的解題思想就是遞歸,所以大同小異啦...

    HelKyle 評論0 收藏0
  • LeetCode 之 JavaScript 解答第94 —— 二叉的中序遍歷

    摘要:小鹿題目二叉樹中序遍歷給定一個二叉樹,返回它的中序遍歷。通常遞歸的方法解決二叉樹的遍歷最方便不過,但是我還是喜歡增加點難度,用一般的迭代循環(huán)來實現(xiàn)。 Time:2019/4/25Title:Binary Tree Inorder TraversalDifficulty: MediumAuthor:小鹿 題目:Binary Tree Inorder Traversal(二叉樹中序遍歷...

    Jason 評論0 收藏0

發(fā)表評論

0條評論

Olivia

|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<