题解 | #二叉搜索树的后序遍历序列#
二叉搜索树的后序遍历序列
https://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd
package main /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * @param sequence int整型一维数组 * @return bool布尔型 */ // 二叉搜索树是指父亲节点大于左子树中的全部节点,但是小于右子树中的全部节点的树 // 后序遍历是指按照 “左子树-右子树-根节点” 的顺序遍历 func VerifySquenceOfBST(sequence []int) bool { // write code here // 约定空树不是二叉搜索树 if len(sequence) == 0 { return false } return check(sequence, 0, len(sequence)-1) } func check(sequence []int, l, r int) bool { // 子树剩一个节点 if l >= r { return true } root := sequence[r] // 代表左子树的最后一个索引位置 var leftLast int // 找到左子树和右子树的分界点 for leftLast = r; leftLast >= l; leftLast-- { if sequence[leftLast] < root { break } } // 判断左子树是否合法 for i := leftLast; i >= l; i-- { if sequence[i] > root { return false } } return check(sequence, l, leftLast) && check(sequence, leftLast+1, r-1) }