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

Anshiii 發布于2019-08-22 18:20 / 2021人閱讀

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

題目描述

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

分析

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

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

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

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

沒有鍵值相等的節點。

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

遞歸實現

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);
}

非遞歸實現

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

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;
    
}

云服務器 GPU云服務器非遞歸二叉樹遍歷二叉樹的遍歷 php樹的遞歸查詢 python實現遞歸

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/95761.html

樹和樹的算法

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

RaoMeng 2019-08-19 11:08 評論0 收藏0
樹和樹的算法

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

PiscesYE 2019-07-30 17:45 評論0 收藏0
二叉樹遍歷

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

aboutU 2019-08-26 13:54 評論0 收藏0