伯爵手表网站,黄的网站建设,wordpress 小说站主题,网站后台认证码不要谩骂以前的自己 他当时一个人站在雾里也很迷茫 —— 24.11.6 1008. 前序遍历构造二叉搜索树 给定一个整数数组#xff0c;它表示BST(即 二叉搜索树 )的 先序遍历 #xff0c;构造树并返回其根。 保证 对于给定… 不要谩骂以前的自己 他当时一个人站在雾里也很迷茫 —— 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但可以大于当前节点值。
返回根节点最终返回构建好的二叉搜索树的根节点。
时间复杂度On
/*** 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;}
}
