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

資訊專欄INFORMATION COLUMN

【刷算法】判斷二叉搜索樹的后序遍歷序列的遞歸實現(xiàn)和非遞歸實現(xiàn)

Anshiii / 2014人閱讀

摘要：題目描述輸入一個整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹的后序遍歷的結(jié)果。那么對于二叉搜索樹的后序遍歷的序列來說，最后一個元素即是它的根節(jié)點，序列的前某部分元素全部小于最后一個元素，序列的后某部分元素全大于最后一個元素。

題目描述

輸入一個整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹的后序遍歷的結(jié)果。如果是則輸出Yes,否則輸出No。假設(shè)輸入的數(shù)組的任意兩個數(shù)字都互不相同。

分析

所謂二叉搜索樹，也稱為二叉搜索樹、有序二叉樹（ordered binary tree）或排序二叉樹（sorted binary tree），是指一棵空樹或者具有下列性質(zhì)的二叉樹：

若任意節(jié)點的左子樹不空，則左子樹上所有節(jié)點的值均小于它的根節(jié)點的值；

若任意節(jié)點的右子樹不空，則右子樹上所有節(jié)點的值均大于它的根節(jié)點的值；

任意節(jié)點的左、右子樹也分別為二叉查找樹；

沒有鍵值相等的節(jié)點。

那么對于二叉搜索樹的后序遍歷的序列來說，最后一個元素即是它的根節(jié)點，序列的前某部分元素全部小于最后一個元素，序列的后某部分元素全大于最后一個元素。然后對于這兩部分來說，又分別符合這些特點，可以遞歸的檢查下去。

遞歸實現(xiàn) 
function VerifySquenceOfBST(s)
{
    if(s.length === 0)
        return false;
    return judge(s, 0, s.length-1);
}

function judge(a, l, r) {
    if(l >= r)
        return true;
    var p1 = r;
    while(p1 > l && a[p1-1] > a[r]) {
        p1--;
    }
    var p2 = p1-1;
    while(p2 >= l){
        if(a[p2] > a[r])
            return false;
        p2--;
    }
    
    return judge(a, l, p1-1) && judge(a, p1, r-1);
}
非遞歸實現(xiàn)

對于一個二叉搜索樹來說，根節(jié)點的左子樹每個節(jié)點的值肯定小于右子樹每個節(jié)點的值，所以可以不斷的去去掉序列的最后一個值，并且把剩下的部分分成小于最后一個值和大于最后一個值的兩部分，只要能分出來那就說明符合二叉搜索樹的定義，否則就不符合。

function VerifySquenceOfBST(s)
{
    if(s.length === 0)
        return false;
    var start = 0, end = s.length-1;
    while(end !== 0) {
        while(s[start] < s[end]){
            start++;
        }
        while(s[start] > s[end]){
            start++;
        }
        
        if(start < end)
            return false;
        end--;
        start  = 0;
    }
    return true;
    
}

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

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

相關(guān)文章

  • 樹和樹的算法

    摘要：樹和樹的算法一樹樹的概念樹英語是一種抽象數(shù)據(jù)類型或是實作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)，用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。一種時間復(fù)雜度額外空間復(fù)雜度的二叉樹的遍歷方式，為二叉樹的節(jié)點個數(shù)。 樹和樹的算法 一、樹 1.1 樹的概念 樹（英語：tree）是一種抽象數(shù)據(jù)類型（ADT）或是實作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)，用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。它是由n（n>=1）個有限節(jié)點組成一個...

    RaoMeng 評論0 收藏0

  • 樹和樹的算法

    摘要：樹和樹的算法一樹樹的概念樹英語是一種抽象數(shù)據(jù)類型或是實作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)，用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。一種時間復(fù)雜度額外空間復(fù)雜度的二叉樹的遍歷方式，為二叉樹的節(jié)點個數(shù)。 樹和樹的算法 一、樹 1.1 樹的概念 樹（英語：tree）是一種抽象數(shù)據(jù)類型（ADT）或是實作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)，用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。它是由n（n>=1）個有限節(jié)點組成一個...

    PiscesYE 評論0 收藏0

  • 二叉樹遍歷

    摘要：前言本篇文章是在二叉排序樹的基礎(chǔ)上進行遍歷查找與刪除結(jié)點。接下來我們根據(jù)構(gòu)造的這顆二叉樹進行相應(yīng)遍歷查找與刪除操作。遍歷二叉樹二叉樹的遍歷分為深度優(yōu)先遍歷和廣度優(yōu)先遍歷。中序遍歷二叉排序樹，得到的數(shù)組是有序的且是升序的。 前言 本篇文章是在二叉排序樹的基礎(chǔ)上進行遍歷、查找、與刪除結(jié)點。 那么首先來看一下什么是二叉排序樹？ 二叉排序樹 定義 二叉排序樹，又稱二叉查找樹、二叉搜索樹。 若...

    aboutU 評論0 收藏0

發(fā)表評論

0條評論

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