BST映射练习题,要求使用Java编程实现,以及具体代码和答案解析如下:
&nbSp; 题目:给出一个整数数组,数组中元素各不相同,请判断数组中的元素能否构成一个BST的后序遍历序列。如果可以,则输出二叉搜索树的根节点;否则输出null。假设输入的数字范围在[0,10^9]之间,且数组长度为n,如果n=0,则输出null。
注意:您必须按顺序构建二叉搜索树(BST),即对于有序数组,我们先构建根节点,然后在左边构建小于根节点的树,右边构建大于根节点的树,并且树的构建是递归进行的。
示例:
输入:[2,1,3],输出:一个根节点值为2,左孩子值为1,右孩子值为3的二叉搜索树。
输入:[4,6,7,5],输出:无法构建,因为4和6、7、5构成的序列不是BST的后续遍历序列。
要求:

1、 编写一个函数 canBeBSTPostorder(seq),输出是否能构成BST的后序遍历序列;
2、 编写一个函数 buildBST(seq),输入为后序遍历序列,如果可以构成BST则构建并返回根节点;否则返回null。
注意:必须使用后续遍历序列构建BST,且构建的树必须是二叉搜索树。
由于返回的是树节点,假设已经定义了树节点类:
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
代码实现要求:
