福永网站优化,汨罗做网站,汕头专业的免费建站,学校网站建设制度题意理解#xff1a; 我们需要根据一个数组来构建一个二叉搜索树#xff0c;且该二叉搜索树也是高度平衡二叉树。 什么是高度平衡二叉树呢? 即对于每个节点来说#xff0c;左右子树高度差不超过1 思路#xff1a;我们总是从数组的中间位置作为根节点构建该树#xff0c;这… 题意理解 我们需要根据一个数组来构建一个二叉搜索树且该二叉搜索树也是高度平衡二叉树。 什么是高度平衡二叉树呢? 即对于每个节点来说左右子树高度差不超过1 思路我们总是从数组的中间位置作为根节点构建该树这样就能保证左子树和右子树节点数目差值不超1。 解题方法 递归 迭代 1.递归
首先明确我们总是先构造根节点然后构造左子树构造右子树。最终返回一棵完整的树。
如果输入的数组为nums长度为0那么返回一个null。
额外补充一点对于数组区间的判定经常会出错可以先规定是左闭右开还是左开右闭然后严格按照约定来执行。
public TreeNode sortedArrayToBST(int[] nums) {if(nums.length0) return null;int mid Math.floorDiv(nums.length,2);TreeNode rootnew TreeNode(nums[mid]);TreeNode leftsortedArrayToBST(Arrays.copyOfRange(nums,0,mid));TreeNode rightsortedArrayToBST(Arrays.copyOfRange(nums,mid1,nums.length));root.leftleft;root.rightright;return root;}//方法二
public TreeNode sortedArrayToBST(int[] nums) {return sortedArrayToSubBST(nums,0,nums.length);}public TreeNode sortedArrayToSubBST(int[] nums,int left,int right) {if(leftright) return null;if(right-left1) return new TreeNode(nums[left]);int mid leftMath.floorDiv((right-left),2);TreeNode rootnew TreeNode(nums[mid]);TreeNode leftNodesortedArrayToSubBST(nums,left,mid);TreeNode rightNodesortedArrayToSubBST(nums,mid1,right);root.leftleftNode;root.rightrightNode;return root;}
2.迭代
迭代法的话需要进行分析。
为了实现迭代我们需要三个来进行维护一个用来维护当前新建节点一个用来数组左子树下标另一个用来维护右子树下标。 public TreeNode sortedArrayToBST2(int[] nums) {QueueTreeNode nodesnew LinkedList();QueueInteger leftIndexnew LinkedList();QueueInteger rightIndexnew LinkedList();//初始化TreeNode rootnew TreeNode();nodes.offer(root);leftIndex.offer(0);rightIndex.offer(nums.length-1);//为了实现迭代使用三个数组while(!nodes.isEmpty()){//创建根节点TreeNode curNodenodes.poll();int leftleftIndex.poll();int rightrightIndex.poll();int midMath.floorDiv((leftright),2);curNode.valnums[mid];//处理左区间if(leftmid-1){curNode.leftnew TreeNode();nodes.offer(curNode.left);leftIndex.offer(left);rightIndex.offer(mid-1);}//处理右区间if(rightmid1){curNode.rightnew TreeNode();nodes.offer(curNode.right);leftIndex.offer(mid1);rightIndex.offer(right);}}return root;}
3.分析 时间复杂度 递归O(n) 迭代O(n) 空间负责度 递归O(n) 迭代O(3n)
