建设营销型网站的步骤,网站怎么维护更新,个人住房公积金贷款,腊肉网站的建设前景根据前序遍历结果构造二叉搜索树-力扣 1008 题
题目说明#xff1a; 1.preorder 长度1 2.preorder 没有重复值 直接插入
解题思路#xff1a; 数组索引[0]的位置为根节点#xff0c;与根节点开始比较#xff0c;比根节点小的就往左边插#xff0c;比根节点大的就往右…根据前序遍历结果构造二叉搜索树-力扣 1008 题
题目说明 1.preorder 长度1 2.preorder 没有重复值 直接插入
解题思路 数组索引[0]的位置为根节点与根节点开始比较比根节点小的就往左边插比根节点大的就往右边插插入的前提是要插入的位置是Null 注意根据前序遍历的结果可以唯一地构造出一个二叉搜索树
对于前序遍历不是太理解的作者推荐适合小白的文章
二叉树的初步认识_加瓦不加班的博客-CSDN博客 // 8 5 1 7 10 /* 8 / \ 5 10 / \ \ 1 7 12 */ // 8 5 1 7 10
/*8/ \5 10/ \ \1 7 12*/
public TreeNode bstFromPreorder(int[] preorder) {//数组索引[0]的位置为根节点TreeNode root insert(null, preorder[0]);for (int i 1; i preorder.length; i) {insert(root, preorder[i]);}return root;
}private TreeNode insert(TreeNode node, int val) {//找到空位了就创建一个新节点将val插入进去if (node null) {return new TreeNode(val);}if(val node.val) {//继续查询空位 如果查询到空位要和父节点建立关系node.left insert(node.left, val);} else if(node.val val){node.right insert(node.right, val);}return node;
}
上限法 解题思路 //依次处理prevorder中每个值返回创建好的节点或者null //1.如果超过上限返回null 作为孩子返回 //2.如果没超过上限创建节点并设置其左右孩子 // 左右孩子完整后返回 //依次处理prevorder中每个值返回创建好的节点或者null
//1.如果超过上限返回null 作为孩子返回
//2.如果没超过上限创建节点并设置其左右孩子
// 左右孩子完整后返回
public TreeNode bstFromPreorder(int[] preorder) {return insert(preorder, Integer.MAX_VALUE);
}int i 0;
private TreeNode insert(int[] preorder, int max) {//递归结束条件if (i preorder.length) {return null;}int val preorder[i];System.out.println(val String.format([%d], max));if (val max) {//如果超过上限返回null 作为孩子返回return null;}//如果没超过上限创建节点并设置其左右孩子TreeNode node new TreeNode(val);i;node.left insert(preorder, node.val); node.right insert(preorder, max); return node;
}
依次处理 prevorder 中每个值, 返回创建好的节点或 null 作为上个节点的孩子 如果超过上限, 返回 null 如果没超过上限, 创建节点, 并将其左右孩子设置完整后返回 i 需要放在设置左右孩子之前意思是从剩下的元素中挑选左右孩子 分治法
解题思路 //分治法 8,5,1,7,10,12 //8根 左5,1,7 右10,12 //5根 左1 右7 //10根 左null 右12 //我们如何去分治呢首先我们找到的是 题目给出的是前序遍历出来的那么我们只要找到比根节点大的数开始就可以区分左、右子树的范围 //分治法 8,5,1,7,10,12
//8根 左5,1,7 右10,12
//5根 左1 右7
//10根 左null 右12//我们如何去分治呢首先我们找到的是 题目给出的是前序遍历出来的那么我们只要找到比根节点大的数开始就可以区分左、右子树的范围
public TreeNode bstFromPreorder(int[] preorder) {return partition(preorder, 0, preorder.length - 1);
}
//int start, int end 告诉处理范围
private TreeNode partition(int[] preorder, int start, int end) {//结束条件if (start end) {return null;}//获取根节点 创建根节点对象TreeNode root new TreeNode(preorder[start]);//跳过根节点开始找左、右子树的范围int index start 1;//条件是一直找到区域的结束while (index end) {//区分左、右子树的范围if (preorder[index] preorder[start]) {break;}index;}//此时 index 就是左、右子树的分界线root.left partition(preorder, start 1, index - 1);root.right partition(preorder, index, end);return root;
} 刚开始 8, 5, 1, 7, 10, 12方法每次执行确定本次的根节点和左右子树的分界线 第一次确定根节点为 8左子树 5, 1, 7右子树 10, 12 对 5, 1, 7 做递归操作确定根节点是 5 左子树是 1 右子树是 7 对 1 做递归操作确定根节点是 1左右子树为 null 对 7 做递归操作确定根节点是 7左右子树为 null 对 10, 12 做递归操作确定根节点是 10左子树为 null右子树为 12 对 12 做递归操作确定根节点是 12左右子树为 null 递归结束返回本范围内的根节点
