【Leetcode】十六、深度优先搜索 & 宽度优先搜索 :二叉树的层序遍历

1、深度优先搜索算法

深度优先搜索,即DFS,从root节点开始,尽可能深的搜索每一个分支。把一个分支的结果搜索完以后,再去看下一个分支。

在这里插入图片描述
应用场景:

  • 二叉树搜索
  • 图搜索

例子:走迷宫,从起点开始,一直走到终点或者撞墙后(这就是所谓的 “深度” 优先),回到起点重新开始,可以找到如下两条路(红色箭头和黄色箭头)

在这里插入图片描述

用深度优先来看前面回溯中提到的子集求法:从起点开始,首先是一个空集。往下有1、2、3三条路可以走
在这里插入图片描述

先逮着1开始走,1符号要求,放入结果集,接着往下走,[1,2],也符合要求,放入结果集,接着往下走,[1,2,3],也符合要求,放入结果集,再往下,就到底了。换另一条路走。

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、5,count = 3,结果集array = [1,2]
  • pop出元素3,加入其左右节点6、7,count = 4,结果集array = [1,2,3]
  • pop出元素4,count = 3,array = [1,2,3,4]
  • pop出元素7,count = 0,array = [1,2,3,4,5,6,7]

3、leetcode102:二叉树的层序遍历

和上面分析的BFS遍历二叉树不一样,这题要求输出的结果是分层的,考虑一层一层的处理,并把每层的处理完的结果加入最终的结果集。

在这里插入图片描述

外层while执行一次,代表处理了二叉树的一层。内层while执行一次,代表处理这层的每个元素(自身出队、左右节点的值入队)

public class P102 {

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (null == root) {
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (queue.size() > 0) {
            // 存每层的结果
            List<Integer> 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解时,每层递归有个level,level = 0,即root节点所在的那层,放到结果集result的0号位置,往下9,放到result的1号元素里面

public class P102 {

    public List<List<Integer>> levelOrderByDfs(TreeNode root) {
        List<List<Integer>> 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, List<List<Integer>> 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 List<List<Integer>> levelOrderBottom(TreeNode root) {
        // 用链表对应的LinkedList
        List<List<Integer>> result = new LinkedList<>();
        if (null == root) {
            return result;
        }
        // 队列
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (queue.size() > 0) {
            int count = queue.size();
            List<Integer> 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.left
        int leftSum = rangeSumBST(root.left, low, high);
        // 右边那一块,新的root就是root.right
        int rightSum = rangeSumBST(root.right, low, high);
        int result = leftSum + rightSum;
        // 中间节点
        if (low <= root.val && root.val <= high) {
            result = result + root.val;
        }
        return result;
    }
}

以上面二叉树为例:

- 第一次递归:root=10, left=5,right=15
- 第二次递归:root=上一层的root.left=5,left=3,right=7
- 第三次递归:root=上一层的root.left=3,left=null,right=null
- 第四次递归:root=上一层的root.left=null,终止递归,回退,返回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;
        Queue<TreeNode> 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;
    }
}

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-21 02:12:02       142 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-21 02:12:02       156 阅读
  3. 在Django里面运行非项目文件

    2024-07-21 02:12:02       131 阅读
  4. Python语言-面向对象

    2024-07-21 02:12:02       141 阅读

热门阅读

  1. 跨平台webSocket模块设计技术解决方案

    2024-07-21 02:12:02       28 阅读
  2. Angular之store全局状态管理 浅学

    2024-07-21 02:12:02       31 阅读
  3. 暗网与深网的技术原理、应用及社会影响探究

    2024-07-21 02:12:02       26 阅读
  4. Spring Cloud Gateway 响应数据加密

    2024-07-21 02:12:02       35 阅读
  5. HTTP爬虫IP流量和数量计费模式选择指南

    2024-07-21 02:12:02       27 阅读
  6. PHP项目开发流程概述

    2024-07-21 02:12:02       28 阅读
  7. Go知识点记录

    2024-07-21 02:12:02       30 阅读
  8. DAY05 CSS

    DAY05 CSS

    2024-07-21 02:12:02      34 阅读
  9. MacOS命令行运行fortran程序|编程私教解答

    2024-07-21 02:12:02       31 阅读
  10. 类与对象-多态-案例3-电脑组装具体实现

    2024-07-21 02:12:02       31 阅读