行业资讯
Leetcode 108,102:将有序数组转化为二叉搜索树，二叉树的层序遍历
1.题目描述题目解答这道题涉及到了二叉搜索树的知识点以及什么是平衡树我们来分开讲解二叉搜索树的特点就是左子节点父节点右子节点对于每一个节点都是这样无特殊情况下的时间复杂度为O(logn),如果退化成了链表的话时间复杂度就会变为O(n)。而平衡树就是指左子树和右子树的高度差1;将这两个结合在一起我们就可以进行推导。无非就是尽量保证两个条件尽量保证每个节点都有左右子树尽量保证左右子树的节点数目相等那么我们可以通过二分递归来解决这两个条件由于我们每次是根据中间值来进行赋值和查找所以可以可以保证我们的左右子节点分布是相对均匀的并且一定会有左右子树可以轻松满足以上的两个条件。classSolution{// 主函数将有序数组转换为平衡二叉搜索树publicTreeNodesortedArrayToBST(int[]nums){// 调用递归区间为整个数组 [0, nums.length-1]returnbulid(nums,0,nums.length-1);}// 递归函数把数组 [left, right] 这段区间转成 BSTpublicTreeNodebulid(int[]nums,intleft,intright){// 递归终止条件区间为空left right没有节点可建了if(leftright){returnnull;}// 取中间位置作为根保证左右元素数量尽量相等从而树是平衡的intmid(leftright)/2;// 用中间元素创建当前子树的根节点TreeNoderootnewTreeNode(nums[mid]);// 递归构建左子树用 [left, mid-1] 这段TreeNodelbulid(nums,left,mid-1);// 递归构建右子树用 [mid1, right] 这段TreeNoderbulid(nums,mid1,right);// 把左子树和右子树挂到根节点上root.leftl;root.rightr;// 返回当前子树的根returnroot;}}2.题目描述题目解答层序遍历可以使用队列就可以很轻松地解决大体思路是将父节点入队再将父节点的所有子节点按照左右的顺序入队之后再将原来的父节点出队并将他们的值存入列表中。剩下的节点就是下一层的所有节点他们会作为新一轮的父节点。如此循环往复直到队列为空后停止循环就得到了完整的列表classSolution{publicListListIntegerlevelOrder(TreeNoderoot){// 队列辅助 BFS先进先出依次存储每一层的节点QueueTreeNodequeuenewLinkedList();// 结果列表外层 List 的每个元素是一层的节点值ListListIntegerlistnewArrayList();// 空树直接返回空列表if(rootnull){returnlist;}// 根节点入队启动 BFSqueue.offer(root);// count 记录当前是第几层从 0 开始intcount0;// 队列空了说明所有层的节点都处理完了while(!queue.isEmpty()){// 当前层的节点数量这个值必须在循环前固定因为循环内会继续入队下一层节点intcurrentsizequeue.size();// 为当前层创建一个空列表list.add(newArrayList());// 逐个处理当前层的所有节点for(inti0;icurrentsize;i){// 弹出队头节点TreeNodecurqueue.poll();// 把当前节点的值加入当前层的列表list.get(count).add(cur.val);// 左子不为空就入队下一层才处理if(cur.left!null){queue.offer(cur.left);}// 右子不为空就入队下一层才处理if(cur.right!null){queue.offer(cur.right);}}// 当前层处理完毕层号加 1count;}returnlist;}}
郑州网站建设
网页设计
企业官网
