每天一道劍指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);  //否則遞歸往下去判斷      }  }

代碼截圖(避免亂碼)