ACM 选手带你玩转二叉树层次遍历(递归 + 非递归)

简介: ACM 选手带你玩转二叉树层次遍历(递归 + 非递归)

大家好呀,我是在第 18 层的帅蛋。


我在之前说过,二叉树遍历的实现历来是面试的高频问题。


这里提到的二叉树遍历一般就是:前序遍历、中序遍历、后序遍历和层次遍历。


关于二叉树的前中后序遍历有两种实现方式:递归和非递归。我在前面两篇文章已经做了介绍:


ACM 选手带你玩转二叉树前中后序遍历(递归版)

ACM 选手带你玩转二叉树前中后序遍历(非递归版)


没看过的小婊贝可以看一下。


今天呢,就来讲剩下的层次遍历。


层次遍历就是表面意思,一层层的遍历,同一层的遍历按照从左到右逐个遍历。

640.png


像上面这个二叉树,它的层次遍历顺序为:ABCDEFGHIJ。


关于二叉树层次遍历,同样也是有递归和非递归两种实现方式,但是层次遍历因为它的遍历属性,和之前的前中后序遍历还是有些不同的

640.png


下面我用一道 LeetCode 的题来给大家具体讲解二叉树层次遍历的递归和非递归方法。


   二叉树层次遍历


LeetCode 102:二叉树的层次遍历


给你一个二叉树,请你返回其按层次遍历得到的节点值。


示例

640.png


递归版


解析


二叉树层次遍历使用递归法,说实话有点反层次遍历的初衷。


人家层次遍历就是要一层一层的遍历,而我们都知道递归是一种解决到底然后再去解决其它问题的特点,也就是深度,就像下面这样:

640.png


既然准备使用递归,那就寄出递归二步曲:


(1) 找出重复的子问题。


层次遍历是每一层的节点从左到右的遍历,所以在遍历的时候我们可以先遍历左子树,再遍历右子树

640.png

可能换成下面这样更清楚点:

640.png


遍历的顺序是:3 -> 9 -> 3 -> 20 -> 15 -> 20 -> 7。


需要注意的是,在遍历左子树或者右子树的时候,涉及到向上或者向下遍历,为了让递归的过程中的同一层的节点放在同一个列表中,在递归时要记录深度 depth


同时,每次遍历到一个新的 depth,结果数组中没有对应的 depth 的列表时,在结果数组中创建一个新的列表保存该 depth 的节点

# 若当前行对应的列表不存在,加一个空列表
if len(res) < depth:
    res.append([])


(2) 确定终止条件。


对于二叉树的遍历来说,想终止,即没东西遍历了,没东西遍历自然就停下来了。


即最下面一层的左右节点都为空了。

if root == None:
    return []


还是那句话,最重要的两点确定完了,那代码也就出来了。


二叉树层次遍历递归版,由于每个节点都被遍历到,所以时间复杂度为 O(n)


此外在递归过程中调用了额外的栈空间,维护了一个 res 的结果数组,所以空间复杂度为 O(n)


代码实现


Python 代码实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def level(self, root: TreeNode, depth, res):
        if root == None:
            return []
        # 若当前行对应的列表不存在,加一个空列表
        if len(res) < depth:
            res.append([])
        # 将当前节点的值加入当前行的 res 中
        res[depth - 1].append(root.val)
        # 递归处理左子树
        if root.left:
            self.level(root.left, depth + 1, res)
        # 递归处理右子树
        if root.right:
            self.level(root.right, depth + 1, res)
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        res = []
        self.level(root, 1, res)
        return res


Java 代码实现

class Solution {
    void level(TreeNode root, int index, List<List<Integer>> res) {
    if(res.size() < index) {
      res.add(new ArrayList<Integer>());
    }
    res.get(index-1).add(root.val);
    if(root.left != null) {
      level(root.left, index+1, res);
    }
    if(root.right != null) {
      level(root.right, index+1, res);
    }
  }
  public List<List<Integer>> levelOrder(TreeNode root) {
    if(root == null) {
      return new ArrayList<List<Integer>>();
    }
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    level(root, 1, res);
    return res;
  }
}

非递归版


解析


非递归版的层次遍历和之前讲的非递归版的前中后序遍历,还是不同的


非递归版的前中后续遍历,是将递归中用的栈光明正大的模拟出来。


非递归版的层次遍历我们用的则是队列,这是由于层次遍历的属性非常契合队列的特点。


队列是一种先进先出(First in First Out)的数据结构,简称 FIFO


如果不太了解队列的,可以看下面这篇文章:


ACM 选手带你玩转栈和队列


思路很简单:


使用队列保存每一层的所有节点,把队列里的所有节点出队列,然后把这些出去节点各自的子节点入队列


以此来完成对每层的遍历。

640.png

# 存储当前层的孩子节点列表
childNodes = []
for node in queue:
    # 若节点存在左孩子,入队
    if node.left:
        childNodes.append(node.left)
    # 若节点存在右孩子,入队
    if node.right:
        childNodes.append(node.right)
# 更新队列为下一层的节点,继续遍历
queue = childNodes


二叉树的层次遍历非递归版,每个节点进出队列各一次,所以时间复杂度为 O(n)


此外,额外维护了一个队列和一个结果数组,所以空间复杂度为 O(n)


代码实现


Python 代码实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if root == None:
            return []
        res = []
        queue = [root]
        while queue:
            res.append([node.val for node in queue])
            # 存储当前层的孩子节点列表
            childNodes = []
            for node in queue:
                # 若节点存在左孩子,入队
                if node.left:
                    childNodes.append(node.left)
                # 若节点存在右孩子,入队
                if node.right:
                    childNodes.append(node.right)
            # 更新队列为下一层的节点,继续遍历
            queue = childNodes
        return res



Java 代码实现


class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> curlevel = new ArrayList<Integer>();
            int curlevelLen = queue.size();
            for (int i = 1; i <= curlevelLen; ++i) {
                TreeNode node = queue.poll();
                curlevel.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            res.add(curlevel);
        }
        return res;
    }
}


到这,二叉树的层次遍历(递归 + 非递归)就讲完啦,大家学废了嘛?


至此,二叉树的四种遍历我都已经完整的介绍了,希望大家能够认真的看完,认真的给我一键三连。


点赞 + 在看 + 转发让我快乐。


640.jpg


我是帅蛋,我们下次见~

相关文章
|
2天前
|
存储 算法 编译器
技术经验解读:二叉树的遍历:先序中序后序遍历的递归与非递归实现及层序遍历
技术经验解读:二叉树的遍历:先序中序后序遍历的递归与非递归实现及层序遍历
|
2月前
|
算法
递归算法:二叉树前序、中序、后序遍历解析与递归思想深度剖析
递归算法:二叉树前序、中序、后序遍历解析与递归思想深度剖析
51 0
一篇文章带你玩转二叉树的层序遍历 | 十道题巩固练习(二)
一篇文章带你玩转二叉树的层序遍历 | 十道题巩固练习
50 0
|
存储 算法
一篇文章带你玩转二叉树的层序遍历 | 十道题巩固练习(一)
一篇文章带你玩转二叉树的层序遍历 | 十道题巩固练习
104 0
|
存储 算法 关系型数据库
重温算法之二叉树的锯齿形层序遍历
关于二叉树的题目其实是我的弱项,虽然二叉树不是很难理解,但是从学校开始接触二叉树开始就对它不是很感冒,所以很多时候都避开它,但是再难咬的骨头也的得啃,二叉树运用在很多程序的底层实现里,比如MySQL的索引实现就是B+树,我们懂得使用索引的同时也得知道,索引为什么这么快,而其快的原因就是底层里B+树得实现。
92 0
重温算法之二叉树的锯齿形层序遍历
|
算法 Java Python
ACM 选手带你玩转二叉树前中后序遍历(递归版)
ACM 选手带你玩转二叉树前中后序遍历(递归版)
ACM 选手带你玩转二叉树前中后序遍历(递归版)
|
Java Python
ACM 选手带你玩转二叉树前中后序遍历(非递归版)
ACM 选手带你玩转二叉树前中后序遍历(非递归版)
ACM 选手带你玩转二叉树前中后序遍历(非递归版)
|
Java Python
ACM 选手图解 LeetCode 从中序与后序遍历构造二叉树
ACM 选手图解 LeetCode 从中序与后序遍历构造二叉树
ACM 选手图解 LeetCode 从中序与后序遍历构造二叉树
|
Java Python
ACM 选手图解 LeetCode 从前序与中序遍历构造二叉树
ACM 选手图解 LeetCode 从前序与中序遍历构造二叉树
ACM 选手图解 LeetCode 从前序与中序遍历构造二叉树
|
Java Python
ACM 选手图解 LeetCode N 叉树的层序遍历
ACM 选手图解 LeetCode N 叉树的层序遍历
ACM 选手图解 LeetCode N 叉树的层序遍历