成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專欄INFORMATION COLUMN

[Leetcode] Verify Preorder Sequence in Binary Sear

未東興 / 2306人閱讀

摘要：如果繼續(xù)降序，說明又向左走了，這樣等到下次向右走得時(shí)候也要再次更新最小值。這樣，序列無效的條件就是違反了這個(gè)最小值的限定。我們同樣可以用本題的方法解，不過是從數(shù)組的后面向前面遍歷，因?yàn)樵诤竺媪?。棧的增長方向也是從高向低了。

Verify Preorder Sequence in Binary Search Tree 
Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree.


You may assume each number in the sequence is unique.


Follow up: Could you do it using only constant space complexity?
棧法 復(fù)雜度

時(shí)間 O(N) 空間 O(N)

思路

二叉搜索樹先序遍歷序列的特點(diǎn)是降序的部分一定是向左走的，一旦開始升序說明開始向右走了，則上一個(gè)降序的點(diǎn)則限定了后面的數(shù)的最小值。如果繼續(xù)降序，說明又向左走了，這樣等到下次向右走得時(shí)候也要再次更新最小值。

    10
   /  
  5    12
 / 
2   6

如這個(gè)例子，我們?cè)?0的位置是沒有最小值限定的，然后降序走到5，依然沒有最小值，降序走到2，依然沒有，然后開始升序了，遇到6，這時(shí)候之后的數(shù)字一定大于2，同時(shí)也大于5，所以最小值更新為之前遍歷過的，且比當(dāng)前數(shù)稍微小一點(diǎn)的那個(gè)數(shù)。這里我們可以用一個(gè)棧來暫存之前的路徑，所以升序時(shí)就是將棧中元素不斷pop出來直到棧頂大于當(dāng)前數(shù)，而最小值就是最后一個(gè)pop出來的數(shù)，最后再把該數(shù)push進(jìn)去。對(duì)于降序的時(shí)候，直接向里面push就行了。這樣，序列無效的條件就是違反了這個(gè)最小值的限定。

代碼 
public class Solution {
    public boolean verifyPreorder(int[] preorder) {
        Stack stk = new Stack();
        // 初始化最小值為最小整數(shù)
        int min = Integer.MIN_VALUE;
        for(int num : preorder){
            // 違反最小值限定則是無效的
            if(num < min) return false;
            // 將路徑中所有小于當(dāng)前的數(shù)pop出來并更新最小值
            while(!stk.isEmpty() && num > stk.peek()){
                min = stk.pop();
            }
            // 將當(dāng)前值push進(jìn)去
            stk.push(num);
        }
        return true;
    }
}
指針模擬棧法 復(fù)雜度

時(shí)間 O(N) 空間 O(N)

思路 
    10
   /  
  5    12
 / 
2   6

同樣是看這個(gè)例子，我們序列是[10, 5, 2, 6, 12]，如果用棧的話，遍歷序列到第n個(gè)數(shù)時(shí)，棧中的情況是這樣的：

1 | 10
2 | 10 5
3 | 10 5 2
4 | 10 6
5 | 12

可見我們棧的大小是不會(huì)超過我們當(dāng)前遍歷的數(shù)的位置的，所以我們大可以用該序列的之前遍歷過的部分來當(dāng)做我們的棧。這里用一個(gè)i指針標(biāo)記棧頂。

注意

這里棧頂指針應(yīng)初始化為-1，這樣棧第一個(gè)元素加入時(shí)，i++后不會(huì)超界

代碼 
public class Solution {
    public boolean verifyPreorder(int[] preorder) {
        // 用i標(biāo)記棧頂
        int i = -1, min = Integer.MIN_VALUE;
        for(int num : preorder){
            if(num < min) return false;
            // 同樣的解法，但是復(fù)用了數(shù)組作為棧，每pop一次相當(dāng)于i--
            while(i >= 0 && num > preorder[i]){
                min = preorder[i--];
            }
            // push相當(dāng)于i++
            preorder[++i] = num;
        }
        return true;
    }
}
后續(xù) Follow Up

Q：如何驗(yàn)證中序序列？
A：中序序列是有序的，只要驗(yàn)證其是否升序的就行了。

Q：如何驗(yàn)證后序序列？
A：后序序列的順序是left - right - root，而先序的順序是root - left - right。我們同樣可以用本題的方法解，不過是從數(shù)組的后面向前面遍歷，因?yàn)閞oot在后面了。而且因?yàn)閺暮笸翱词窍扔龅絩ight再遇到left，所以我們要記錄的是限定的最大值，而不再是最小值，棧pop的條件也變成pop所有比當(dāng)前數(shù)大得數(shù)。棧的增長方向也是從高向低了。

    public boolean IsValidPostOrderBst(int[] nums)
    {
        int i = nums.length;
        int max = Integer.MAX_VALUE;
        for (int j = nums.length - 1; j >= 0; j--)
        {
            if (nums[j] > max) return false;
            while (i <= nums.length - 1 && nums[j] > nums[i])
                max = nums[i++];
            nums[--i] = nums[j];
        }
        return true;
    }

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/64693.html

相關(guān)文章

  • leetcode331. Verify Preorder Serialization of a Bi

    摘要：如果我們從右往左看先序遍歷，就知道后兩個(gè)節(jié)點(diǎn)如果遇到第三個(gè)節(jié)點(diǎn)，則該節(jié)點(diǎn)就應(yīng)當(dāng)是這兩個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)。如果在遍歷的過程中根節(jié)點(diǎn)數(shù)量小于，則說明這棵樹有問題。而如果遍歷結(jié)束之后，剩下的根節(jié)點(diǎn)數(shù)不等于，也說明這個(gè)先序遍歷存在問題。 題目要求 One way to serialize a binary tree is to use pre-order traversal. When we en...

    weapon 評(píng)論0 收藏0

  • LeetCode 331. Verify Preorder Serialization of a B

    摘要：如果它是一個(gè)空節(jié)點(diǎn)，我們可以使用一個(gè)標(biāo)記值記錄，例如。例如，上面的二叉樹可以被序列化為字符串，其中代表一個(gè)空節(jié)點(diǎn)。每個(gè)以逗號(hào)分隔的字符或?yàn)橐粋€(gè)整數(shù)或?yàn)橐粋€(gè)表示指針的。如果滿足前序遍歷，那么最后棧中有且僅有一個(gè)元素，且是。 Description One way to serialize a binary tree is to use pre-order traversal. When ...

    張巨偉 評(píng)論0 收藏0

  • Verify Preorder Serialization of a Binary Tree

    摘要：令，那么從累加會(huì)一直保持正，最后為。從左往右比較好理解，因?yàn)榭偸强偟阶笤俚接遥目偸堑?，所以一定是保持。注意從開始，因?yàn)闆]有。 Verify Preorder Serialization of a Binary Tree 題目鏈接：https://leetcode.com/problems... recursion，用個(gè)全局的index： public class Solution {...

    melody_lql 評(píng)論0 收藏0

  • leetcode449. Serialize and Deserialize BST

    摘要：題目要求將二叉搜索樹序列化和反序列化，序列化是指將樹用字符串的形式表示，反序列化是指將字符串形式的樹還原成原來的樣子。假如二叉搜索樹的節(jié)點(diǎn)較多，該算法將會(huì)占用大量的額外空間。 題目要求 Serialization is the process of converting a data structure or object into a sequence of bits so that...

    Honwhy 評(píng)論0 收藏0

  • [LeetCode] 109. Convert Sorted List to Binary Sear

    Problem Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST. For this problem, a height-balanced binary tree is defined as a binary tree in whi...

    dongfangyiyu 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

閱讀需要支付1元查看
<