二叉树的广度优先(层次)遍历

编程算法

字数统计: 237阅读时长: 1 min

 2020/03/30   Share

前言

上篇讲的是二叉树的三种遍历方式，前中后序遍历方式，它们都属于深度优先遍历，所谓深度优先就是沿着树的深度遍历树的节点。而广度优先遍历则是从root开始，从左到右从上到下水平遍历树的节点，所以又称为层次遍历。
深度优先借助的数据结构为栈，而广度优先借助的则是队列。

正文

广度优先遍历

由于在LeetCode中并没有找到相应的题目，所以我直接给出代码。
python代码如下

def breadthTraversal(self,root):
        if root is None:
            return
        else:
            queue = []
            res = []
            queue.append(root)
            while queue:
                node = queue.pop(0)
                res.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            return res

总结

二叉树的广度优先遍历较为简单，只要借助队列，让节点先进先出，便可得到层次遍历的结果。

原文作者：Zer0e

原文链接：https://re0.top/2020/03/30/tree-traversal2/

发表日期：三月 30日 2020, 5:10:00 下午

更新日期：March 30th 2020, 5:02:34 pm

Next Post

浅谈动态规划
Previous Post

二叉树的前中后序遍历

CATALOG

1. 前言
2. 正文
1. 2.1. 广度优先遍历
3. 总结

