每天一道劍指offer-二叉搜索樹的後序遍歷序列
- 2019 年 10 月 4 日
- 筆記
前言
今天的題目 每天的題目見github(看最新的日期): https://github.com/gzc426 具體的題目可以去牛客網對應專題去找。
昨天的題解
題目
每天一道劍指offer-二叉搜索樹的後序遍歷序列 來源: https://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd?tpId=13&tqId=11176&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
題目詳述
輸入一個整數數組,判斷該數組是不是某二叉搜索樹的後序遍歷的結果。如果是則輸出Yes,否則輸出No。假設輸入的數組的任意兩個數字都互不相同。
題目詳解
思路
- 遞歸的思想,每次去判斷左子樹的最右邊界是不是大於右子樹的最左邊界,如果大於就不是,如果小於,那麼就再往下遞歸。
代碼
public class Solution { public boolean VerifySquenceOfBST(int [] sequence) { if(sequence.length == 0) return false; return verify(sequence,0,sequence.length-1); } public boolean verify(int [] sequence,int begin,int end) { if(begin == end) return true; int rootValue = sequence[end]; int leftBegin = -1;//左子樹的左邊界 int leftEnd = -1;//左子樹的右邊界 int rightBegin = -1;//右子樹的左邊界 int rightEnd = -1;//右子樹的右邊界 if(sequence[begin] < rootValue)// 說明存在左子樹,二叉搜索樹的性質 leftBegin = begin;//記錄左子樹的左邊界 for(int i=begin;i<end;i++) { if(sequence[i] < rootValue)//如果比根結點的值小,說明就是左子樹 leftEnd = i;//記錄下來左子樹的右邊界,只要比根結點小,就進行記錄 else{ if(rightBegin == -1) //記錄右子樹的左邊界,這個條件判斷只會記錄一次。 rightBegin = i; rightEnd = i;//記錄右子樹的右邊界 } } if(rightBegin < leftEnd && rightBegin != -1) return false;//如果左子樹的右邊界 大於 右子樹的左邊界 就出問題了!false return verify(sequence,leftBegin,leftEnd) && verify(sequence,rightBegin,rightEnd); //否則遞歸往下去判斷 } }
代碼截圖(避免亂碼)