数据结构与算法——Java实现 54.力扣1008题——前序遍历构造二叉搜索树
1008. 前序遍历构造二叉搜索树
给定一个整数数组，它表示BST(即 二叉搜索树 )的 先序遍历 ，构造树并返回其根。
保证 对于给定的测试用例，总是有可能找到具有给定需求的二叉搜索树。
二叉搜索树 是一棵二叉树，其中每个节点，
Node.left的任何后代的值 严格小于Node.val,Node.right的任何后代的值 严格大于Node.val。二叉树的 前序遍历 首先显示节点的值，然后遍历
Node.left，最后遍历Node.right。示例 1：
输入：preorder = [8,5,1,7,10,12] 输出：[8,5,10,1,7,null,12]示例 2:
输入: preorder = [1,3] 输出: [1,null,3]提示：
1 <= preorder.length <= 1001 <= preorder[i] <= 10^8preorder中的值 互不相同
方法1 遍历插入法
题目中输入的（先）前序遍历序列表示：根 - 左 - 右 进行遍历，输入后应输出构建好的二叉搜索树节点的层序遍历序列，按照前序遍历的结果进行逐个插入
先序遍历数组构建了一个二叉搜索树。bstFromPreorder 方法负责初始化根节点并遍历数组，insert 方法负责将每个元素插入合适的位置
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode bstFromPreorder(int[] preorder){
// preorder 前序遍历结果
TreeNode root = new TreeNode(preorder[0]);
for (int i = 1; i < preorder.length; i++) {
int val = preorder[i];
insert(root,val);
}
return root;
}
private TreeNode insert(TreeNode node, int val) {
if (node == null){
return new TreeNode(val);
}
if (val < node.val){
node.left = insert(node.left,val);
} else if (val > node.val) {
node.right = insert(node.right,val);
}
return node;
}
}
方法2 上限法
1.遍历前序遍历结果数组中每一个值，根据值创建节点，以当前节点作为左右子树的上下限，进行插入判断，分别对各个孩子及上层节点进行判断，然后将各个子树创建完成，最后合并成一个整树
每个节点若成功创建都有：左孩子上限，右孩子上限
2.处理下一个值时，如果超过此上限，那么
① 将 null 作为上个节点的孩子
② 不能创建节点对象
③ 直到不超过上限为止
3.重复 1.2. 两步
解题过程
- 初始化：定义一个全局索引变量i，用于跟踪当前处理的前序数组中的位置。
- 主函数：调用insert方法，初始最大值设为Integer.MAX_VALUE。
- 递归插入：
- 检查当前索引是否超出数组长度，如果是则返回null。
- 获取当前索引处的值val。
- 如果val大于当前允许的最大值max，则返回null（因为这违反了二叉搜索树的性质）。
- 创建新节点，并递归地构建其左子树（左子树的所有节点值都必须小于当前节点值），然后构建右子树（右子树的所有节点值都必须小于max但可以大于当前节点值）。
- 返回根节点：最终返回构建好的二叉搜索树的根节点。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
int i = 0;
public TreeNode bstFromPreorder(int[] preorder) {
return insert(preorder,Integer.MAX_VALUE);
}
private TreeNode insert(int[] preorder ,int max){
if(i == preorder.length){
return null;
}
int val = preorder[i];
if(val > max){
return null;
}
TreeNode node = new TreeNode(val);
i++;
node.left = insert(preorder,val);
node.right = insert(preorder,max);
return node;
}
}
方法3 分治法递归
根据前序遍历中的结果确定根节点，小于根节点的为左子树，大于根节点的为右子树，将左子树和右子树分别递归代入以上判断步骤中，直至判断完所有元素
分而治之思想
前序遍历的第 1 个结点一定是二叉树的根结点；
由于构造出来的是 BST，第 1 个结点后面被分成了两个子区间：
第 1 个子区间里所有的元素都严格小于根结点 -> 递归构建成根结点的左子树；
第 2 个子区间里所有的元素都严格大于根结点 -> 递归构建成根结点的右子树。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class Solution {
public TreeNode bstFromPreorder(int[] preorder) {
int len = preorder.length;
if (len == 0) {
return null;
}
return buildBST(preorder, 0, len - 1);
}
/**
* 使用 preorder 的子区间 [left, right] 构建二叉树
*
* @param preorder
* @param left
* @param right
* @return
*/
private TreeNode buildBST(int[] preorder, int left, int right) {
if (left > right) {
return null;
}
TreeNode root = new TreeNode(preorder[left]);
if (left == right) {
return root;
}
int i = left;
while (i + 1 <= right && preorder[i + 1] < preorder[left]) {
i++;
}
// 此时子区间 [left + 1..i] 所有元素都 < preorder[left]
// [i + 1..right] 所有元素都 > preorder[left]
TreeNode leftTree = buildBST(preorder, left + 1, i);
TreeNode rightTree = buildBST(preorder, i + 1, right);
root.left = leftTree;
root.right = rightTree;
return root;
}
}
