上海网站建设服务是什么意思,北京工地网站建设,网站如何做友情链接,株洲网站建设团队文章目录 1、深度优先搜索算法2、宽度优先搜索算法3、leetcode102#xff1a;二叉树的层序遍历4、leetcode107#xff1a;二叉树的层序遍历II5、leetcode938#xff1a;二叉搜索树的范围和 1、深度优先搜索算法
深度优先搜索#xff0c;即DFS#xff0c;从root节点开始二叉树的层序遍历4、leetcode107二叉树的层序遍历II5、leetcode938二叉搜索树的范围和 1、深度优先搜索算法
深度优先搜索即DFS从root节点开始尽可能深的搜索每一个分支。把一个分支的结果搜索完以后再去看下一个分支。 应用场景
二叉树搜索图搜索
例子走迷宫从起点开始一直走到终点或者撞墙后这就是所谓的 “深度” 优先回到起点重新开始可以找到如下两条路红色箭头和黄色箭头 用深度优先来看前面回溯中提到的子集求法从起点开始首先是一个空集。往下有1、2、3三条路可以走
先逮着1开始走1符号要求放入结果集接着往下走[12]也符合要求放入结果集接着往下走[123]也符合要求放入结果集再往下就到底了。换另一条路走。
2、宽度优先搜索算法
宽度广度优先搜索即BFS和DFS不同BFS是一层一层的处理。BFS一般搭配队列使用。 BFS和DFS的对比 以从上到下、从左到右遍历以下二叉树为例采用宽度优先搭配一个队列先进先出计数count 0。从root开始root入队count 1出队同时root的左、右节点入队并维护count。当count 0时说明遍历结束。 即node.val出队node.left和node.right入队。详细
root节点1入队count 1根据count从队列中pop元素得到root节点把其值val放入结果集并把其左右孩子加进来。结果集array [1]此时队列中存着2、3这两个节点count 2继续根据count 2来pop两次并加入元素的左右孩子pop出元素2加入其左右节点4、5count 3结果集array [12]pop出元素3加入其左右节点6、7count 4结果集array [123]pop出元素4count 3array [1234]…pop出元素7count 0array [1234567]
3、leetcode102二叉树的层序遍历
和上面分析的BFS遍历二叉树不一样这题要求输出的结果是分层的考虑一层一层的处理并把每层的处理完的结果加入最终的结果集。 外层while执行一次代表处理了二叉树的一层。内层while执行一次代表处理这层的每个元素自身出队、左右节点的值入队
public class P102 {public ListListInteger levelOrder(TreeNode root) {ListListInteger result new ArrayList();if (null root) {return result;}QueueTreeNode queue new LinkedList();queue.add(root);while (queue.size() 0) {// 存每层的结果ListInteger list new ArrayList();// 每处理完一层队列的长度即是下一层元素的数量int count queue.size();// 处理每一层的元素弹出这一层的每个元素并把每个元素的左右节点加进去while (count 0) {TreeNode node queue.poll();list.add(node.val);count--;// 弹出的元素的左右孩子节点的值入队if (node.left ! null) {queue.add(node.left);}if (node.right ! null) {queue.add(node.right);}}// 一层处理结束把结果加到结果集里注意别直接add上面的list防止引用传递用copy值传递result.add(new ArrayList(list));}return result;}
}这题很明显的有”层“的概念用BFS很合适但DFS也能解。
从root开始一条路往下走和前面一层层的取不一样了DFS解时每层递归有个levellevel 0即root节点所在的那层放到结果集result的0号位置往下9放到result的1号元素里面
public class P102 {public ListListInteger levelOrderByDfs(TreeNode root) {ListListInteger result new ArrayList();if (null root) {return result;}dfs(root, result, 0);return result;}/*** 深度优先** param node 节点* param result 最终的结果集* param level 二叉树中当前的层级*/public static void dfs(TreeNode node, ListListInteger result, int level) {// 终止条件if (node null) {return;}// 如果当前层级到了2那结果集里应该初始化出两个元素每层的结果存一个结果集的元素里if (level result.size() - 1) {result.add(new ArrayList());}// 层级所在结果集的位置上加入这个元素result.get(level).add(node.val);if (node.left ! null) {dfs(node.left, result, level 1);}if (node.right ! null) {dfs(node.right, result, level 1);}}
}
4、leetcode107二叉树的层序遍历II 和前面102题不同的是要求从叶子节点开始一层层的遍历输出的顺序刚好相反当然可以在102的代码的末尾直接reverse翻转答案然后return。
说起翻转也可自己用栈实现但除了翻转有更优实现结果集result用一个链表依旧从root节点那一层开始从上往下一层层处理但每层的结果加到result的头部如此从上到下遍历完每层后直接不用翻转就是题解。
Java中List里面底层是链表的就不能用ArrayList数组而是LinkedList
public class P107 {public ListListInteger levelOrderBottom(TreeNode root) {// 用链表对应的LinkedListListListInteger result new LinkedList();if (null root) {return result;}// 队列QueueTreeNode queue new LinkedList();queue.add(root);while (queue.size() 0) {int count queue.size();ListInteger levelList new ArrayList();for (int i 0; i count; i) {TreeNode node queue.poll();levelList.add(node.val);if (node.left ! null) {queue.add(node.left);}if (node.right ! null) {queue.add(node.right);}}// 注意这里每次add的下标是0即链表队首这样第二层的结果就会排到第一层result.add(0, levelList);}return result;}
}
以上实现注意链表的巧妙之处 这题要不用BFS而DFS那最后就得reverse翻转一下结果集了。虽然BFS能解的DFS也能解但这种层级的遍历BFS更好用。
最后以上用到的TreeNode
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;}
}5、leetcode938二叉搜索树的范围和
第一反应是遍历二叉树判断每个元素在范围就累加。那应该想到BFS除了BFS还有别的实现不管是前序、中序、后序遍历一个树最后肯定会被拆解成一个个只有三个节点的小块即递归。 解法一普通递归 从root开始一分为二的看最终结果 左 中 右左边有子树的话继续左 中 右纯递归递归终止的条件为节点没有子节点了。代码实现
public class P938 {public int rangeSumBST(TreeNode root, int low, int high) {if (null root) {return 0;}// 左边那一块新的root就是root.leftint leftSum rangeSumBST(root.left, low, high);// 右边那一块新的root就是root.rightint rightSum rangeSumBST(root.right, low, high);int result leftSum rightSum;// 中间节点if (low root.val root.val high) {result result root.val;}return result;}
}以上面二叉树为例
- 第一次递归root10, left5right15
- 第二次递归root上一层的root.left5left3right7
- 第三次递归root上一层的root.left3leftnullrightnull
- 第四次递归root上一层的root.leftnull终止递归回退返回0解法二BFS 一层层的来平铺扫荡每一个出队的元素判断是否在范围内是则累加 这题的BFS和BFS概念分析时一样都不用像前两道题一样分层一层while就行
public class P938 {public int rangeSumBSTByBFS(TreeNode root, int low, int high) {if (null root) {return 0;}int result 0;QueueTreeNode queue new LinkedList();queue.add(root);while (!queue.isEmpty()) {TreeNode node queue.poll();if (node.val low node.val high) {result result node.val;}// 左右节点处理if (node.left ! null) {queue.add(node.left);}if (node.right ! null) {queue.add(node.right);}}return result;}
}
