数据结构与算法——Java实现 54.力扣1008题——前序遍历构造二叉搜索树
不要谩骂以前的自己
他当时一个人站在雾里也很迷茫
—— 24.11.6
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 方法负责将每个元素插入合适的位置
时间复杂度：O(n) = n * logn
/*** 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值，那么
① 将 null 作为上个节点的孩子
② 不能创建节点对象
③ 直到不超过上限为止
3.重复 1.2. 两步
解题过程
- 初始化：定义一个全局索引变量i，用于跟踪当前处理的前序数组中的位置。
- 主函数：调用insert方法，初始最大值设为Integer.MAX_VALUE。
- 递归插入：
- 检查当前索引是否超出数组长度，如果是则返回null。
- 获取当前索引处的值val。
- 如果val大于当前允许的最大值max，则返回null（因为这违反了二叉搜索树的性质）。
- 创建新节点，并递归地构建其左子树（左子树的所有节点值都必须小于当前节点值），然后构建右子树（右子树的所有节点值都必须小于max但可以大于当前节点值）。
- 返回根节点：最终返回构建好的二叉搜索树的根节点。
时间复杂度：O（n）
/*** 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 Solution {public TreeNode bstFromPreorder(int[] preorder) {int len = preorder.length;if (len == 0) {return null;}return partition(preorder, 0, len - 1);}// 使用 preorder 的子区间 [left, right] 构建二叉树private TreeNode partition(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]root.left = partition(preorder, left + 1, i);root.right = partition(preorder, i + 1, right);return root;}
}