23 圖解劍指Offer 二叉搜尋樹的後序周遊序列 Java題解
- 23 圖解劍指Offer 二叉搜尋樹的後序周遊序列 Java題解
-
-
- 題目連結
- 題目描述
- 題解:
- 圖解:
- 代碼:
- 複雜度
-
23 圖解劍指Offer 二叉搜尋樹的後序周遊序列 Java題解
題目連結
題目描述
輸入一個整數數組,判斷該數組是不是某二叉搜尋樹的後序周遊的結果。如果是則輸出Yes,否則輸出No。假設輸入的數組的任意兩個數字都互不相同。
題解:
(1)已知二叉搜尋樹的後序周遊序列,由于二叉搜尋樹left<root<right, 是以 int[] arr = seq.clone();
Arrays.sort(arr);将後序序列按照從小到大排序即可得到二叉搜尋樹的中序序列。
(2) 如果後序序列是中序列的棧彈出序列即可驗證,後序序列是該二叉搜尋樹的後序序列。
(3) 是以先獲得二叉搜尋樹的中序序列,然後在調用之前寫的判斷棧的彈出序列方法,傳回該方法的值。
圖解:
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLiAzNfRHLGZkRGZkRfJ3bs92YsYTMfVmepNHLzEkaOl3YE1UNNpHW4Z0MMBjVtJWd0ckW65UbM5WOHJWa5kHT20ESjBjUIF2X0hXZ0xCMx81dvRWYoNHLrdEZwZ1Rh5WNXp1bwNjW1ZUba9VZwlHdssmch1mclRXY39CXldWYtlWPzNXZj9mcw1ycz9WL49zZuBnL0cTO5EzMzcTM5IjNwAjMwIzLc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)
代碼:
import java.util.Stack;
import java.util.Arrays;
public class Solution {
public boolean VerifySquenceOfBST(int [] seq) {
int[] arr = seq.clone();
Arrays.sort(arr);
return IsPopOrder(arr,seq);
}
//判斷第二個序列是否可能為第一個序列的彈出順序,引用的“棧的壓入、彈出序列”題目的答案
public boolean IsPopOrder(int [] pushA,int [] popA) {
if(pushA.length == 0 || popA.length == 0)
return false;
Stack<Integer> s = new Stack<Integer>();
//用于辨別彈出序列的位置
int popIndex = 0;
for(int i = 0; i< pushA.length;i++){
s.push(pushA[i]);
//如果棧不為空,且棧頂元素等于彈出序列
while(!s.empty() &&s.peek() == popA[popIndex]){
//出棧
s.pop();
//彈出序列向後一位
popIndex++;
}
}
return s.empty();
}
}
複雜度
空間複雜度: 空間複雜度為O(n) 和 二叉樹節點個數有關。
最壞時間複雜度: 時間複雜度 for循環 while循環:O(n2)