题解 | #二叉搜索树的后序遍历序列 java#
二叉搜索树的后序遍历序列
https://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd
import java.util.*; public class Solution { public boolean isAfterOrder(int []sequence, int l, int r) { // foolproof if (l >= r) return true; int root = sequence[r]; int j = r - 1; // get right range while (j >= 0 && sequence[j] > root) { j--; } // check right range is litter than root for (int i = l; i <=j; i++) { // return false if (sequence[i] > root) return false; } // l--> j, j+1 --> r-1 return isAfterOrder(sequence, l, j) && isAfterOrder(sequence, j+1, r-1); } public boolean VerifySquenceOfBST(int [] sequence) { if (sequence == null || sequence.length == 0) { return false; } int left = 0; int right = sequence.length - 1; return isAfterOrder(sequence, left, right); } }
解题思路:
如果这个序列array是一个二叉搜索树的后续遍历,那么必定会满足4个条件:
- root一定在序列末尾,array[len-1]
- 在中间的某个节点 j可以满足 array[0:j+1] < root 这部分区域是左子树的区域; array[j+1: len-1] > root // 题干中提到这里的每个元素都不相同, 所以不存在等于的情况;
- 由于二叉树是递归的结构; 因此 在 array[0:j+1] 和 array[j+1,len-1]区域已经可以再次划分出满足条件的左右子树的区域
因此在写的时候, 可以先做一个区域中找出 j的位置, 然后在检查另一个区域是否满足条件
note_coding 文章被收录于专栏
记录自己的解题思路, 欢迎评价