題目描述

輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹的后序遍歷的結(jié)果。如果是則輸出Yes,否則輸出No。假設(shè)輸入的數(shù)組的任意兩個(gè)數(shù)字都互不相同。

解題思路

先找到右子樹的開始位置，然后分別進(jìn)行左右子樹遞歸處理。

（1）尋找右子樹的開始位置

? 在二叉搜索樹的后序遍歷結(jié)果中，最后一個(gè)元素為這棵樹的根節(jié)點(diǎn)；因此，將最后一個(gè)元素作為比較的標(biāo)準(zhǔn)值，將結(jié)果數(shù)組分為兩段，若后序遍歷結(jié)果正確，則比最后一個(gè)元素小的那一段連續(xù)數(shù)組則為該樹的左子樹，而比最后一個(gè)元素大的那一段連續(xù)數(shù)組則為該樹的右子樹。

? 因此，我們可以得到右子樹的開始位置，即出現(xiàn)的第一個(gè)比 最后一個(gè)元素 大的元素的位置。

（2）后半段數(shù)組的校驗(yàn)

? 如果后半段數(shù)組中，有出現(xiàn)比 最后一個(gè)元素 大的元素，則該結(jié)果不是二叉搜索樹的后序遍歷結(jié)果，返回為 false。

（2）遞歸處理

? 遞歸處理，直到?jīng)]有出現(xiàn) false，最終走到底，返回 true。

代碼實(shí)現(xiàn)

import java.util.Arrays;public class Solution {public boolean VerifySquenceOfBST(int [] sequence) {if (null == sequence || 0 == sequence.length) {return false;}int restart = 0;int length = sequence.length;for (int i = 0; i < length - 1; i++) {if (sequence[i] < sequence[length - 1]) {restart++;}}if (0 == restart) {VerifySquenceOfBST(Arrays.copyOfRange(sequence, 0, length - 1));} else {for (int i = restart; i < length - 1; i++) {if (sequence[i] <= sequence[length - 1]) {return false;}}VerifySquenceOfBST(Arrays.copyOfRange(sequence, 0, restart));VerifySquenceOfBST(Arrays.copyOfRange(sequence, restart, length - 1));}return true;} }

總結(jié)

以上是生活随笔為你收集整理的剑指offer（Java实现） 二叉搜索树的后序遍历序列的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。