C/Golang剑指offer24二叉搜索树的后序遍历序列详解

题目

地址&＃xff1a;https://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd

思路

• 根节点的值大于左子树小于右子树
• 后序遍历: 左子树 -> 右子树 -> 根节点

关键&＃xff1a;最后一个元素是根节点&＃xff0c;找到他的左子树和右子树&＃xff0c;递归判断。

Golang 代码

package mainimport "fmt"func main() {fmt.Printf("VerifySquenceOfBST([]int{5, 7, 6, 9, 11, 10, 8})&＃61;%#v\n", VerifySquenceOfBST([]int{5, 7, 6, 9, 11, 10, 8}))fmt.Printf("VerifySquenceOfBST([]int{7,4,5,6})&＃61;%#v\n", VerifySquenceOfBST([]int{7, 4, 5, 6}))
}func VerifySquenceOfBST(sequence []int) bool {if sequence &＃61;&＃61; nil || len(sequence) <&＃61; 0 {return false}length :&＃61; len(sequence)root :&＃61; sequence[length-1]//get left treel :&＃61; 0for ; l < length-1; l&＃43;&＃43; {if root < sequence[l] {break}}//verify right tree.r :&＃61; lfor ; r < length-1; r&＃43;&＃43; {if root > sequence[r] {return false}}left :&＃61; trueif l > 0 {left &＃61; VerifySquenceOfBST(sequence[:l])}right :&＃61; trueif r < length-1 {right &＃61; VerifySquenceOfBST(sequence[l:length])}return left && right
}


C 代码

#include
#define bool int
#define true 1
#define false 0
//reference:https://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd
bool verify_post_BST(int seq[], int len) {if (seq &＃61;&＃61; NULL || len <&＃61; 0) {return false;}int root &＃61; seq[len - 1];//get left treeint l &＃61; 0;for (; l < len - 1; l&＃43;&＃43;) {if (root < seq[l]) {break;}}//get right tree.int r &＃61; l;for (; r < len - 1; r&＃43;&＃43;) {if (root > seq[r]) {return false;}}bool left &＃61; true;if (l > 0) {left &＃61; verify_post_BST(seq, l);}bool right &＃61; true;if (r < len - 1) {right &＃61; verify_post_BST(seq &＃43; l, len - l - 1);}return left && right;
}
int main() {int seq1[] &＃61; {5, 7, 6, 9, 11, 10, 8};bool r1 &＃61; verify_post_BST(seq1, 7);int seq2[] &＃61; {7,4,5,6};bool r2 &＃61; verify_post_BST(seq2, 4);printf("r1&＃61;%d\n", r1);printf("r2&＃61;%d\n", r2);return 0;
}