题解 | #二叉搜索树的后序遍历序列#
二叉搜索树的后序遍历序列
https://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd
import java.util.*; public class Solution { public boolean VerifySquenceOfBST(int [] sequence) { if(sequence.length == 0) return false; return reverse(sequence); } public boolean reverse(int[] sequence){ //base case if(sequence.length <= 1) return true; //找到根节点 int root = sequence[sequence.length - 1]; //找分界点 int index = 0; while(index < sequence.length - 1){ if(sequence[index] > root){ break; } index++; } //此时,index左边(左子树)都小于根节点,右子树待校验 //进行校验 int tmp = index; while(tmp < sequence.length - 1){ if(sequence[tmp] < root){ return false; } tmp++; } //递归校验左子树 boolean left = reverse(Arrays.copyOfRange(sequence,0,index)); //递归校验右子树 boolean right = reverse(Arrays.copyOfRange(sequence,index,sequence.length - 1)); return left && right; } }
思路:
- 二叉搜索树,可以想到二叉搜索树的特征。左子树所有节点值<根节点<右子树所有节点值
- 后序遍历,数组最后一位是根节点。
- 根据1的性质找到数组的分界点,分界点左边代表左子树,右边代表右子树
- 对左右子树分别进行递归验证