##題目描述 輸入一個整數陣列，判斷該陣列是不是某二叉搜索樹的后序遍歷的結果，如果是則輸出Yes,否則輸出No，假設輸入的陣列的任意兩個數字都互不相同，
思路
分治法，
不斷地確定出左子樹區間和右子樹區間，并且判斷：左子樹區間的所有結點值 < 根結點值 < 右子樹區間所有結點值，
序列最后一個數是根節點，序列第一個大于根節點的數是潛在的右子樹第一個結點，
時間復雜度O(n2)，空間復雜度O(n)，
代碼1
public class Solution {
private boolean helper(int[] sequence, int start, int root) {
if(start >= root) return true;
// 代碼1為兩段區域回圈，mid的初始值容易出錯，代碼2的全域回圈不存在這個問題
int mid = root-1;
for(int i = start; i < root; i++) {
if(sequence[i] > sequence[root]) {
mid = i;
break;
}
}
for(int j = mid+1; j < root; j++) {
if(sequence[j] < sequence[root]) {
return false;
}
}
return helper(sequence, start, mid-1) && helper(sequence, mid, root-1);
}
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence == null || sequence.length == 0) return false;
return helper(sequence, 0, sequence.length - 1);
}
}
代碼2
private boolean helper(int[] sequence, int start, int root) {
if(start >= root) return true;
int mid;
for(mid = start; mid < root; mid++) {
if(sequence[mid] > sequence[root]) {
break;
}
}
for(int j = mid+1; j < root; j++) {
if(sequence[j] < sequence[root]) {
return false;
}
}
return helper(sequence, start, mid-1) && helper(sequence, mid, root-1);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/85164.html
標籤：其他
上一篇：從上往下列印二叉樹