讲透树2 | 树的遍历复盘专题

# 二叉树
class TreeNode(object):
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# N叉树
class Node(object):
    def __init__(self, val=None, children=[]):
        self.val = val
        self.children = children

看起来区别是二叉树的左右孩子和 N叉树的孩子们结点的区别，其实本质是一样的，同理二叉树的左右孩子也能写成children列表的形式。

即：

# 二叉树
class TreeNode(object):
    def __init__(self, val, children=[]):
        self.val = val
        self.children = children

而这里二叉树的 children 只有两个孩子，即左孩子 left 和右孩子 right。

描述完上述的孩子结点的定义，下面再看看递归的遍历方式。

# 二叉树
res = []
def pre_order(root):
    if not root:
        return
    res.append(root.val)
    pre_order(root.left)
    pre_order(root.right)
    
# N叉树
res = []
def pre_order(root):
    if not root:
        return
    res.append(root.val)
    for node in root.children:
        pre_order(node)

看出区别了吗？区别就在 res.append(root.val) 之后的代码。

二叉树的写法是先递归左孩子，再递归右孩子。

N叉树的写法是，利用 for 循环，依次递归孩子结点。

所以，区别就是递归的写法，二叉树写两次递归，N叉树写N次递归

都是一样的逻辑，是不是很简单。类似于先序遍历，其中中序遍历和后续遍历，都是同样的逻辑去处理（N叉树，N可代表从2到n）

github 查看详细代码：https://github.com/xiaozhutec/share_leetcode

4 非递归遍历

非递归遍历先序、中序和后续遍历的详细逻辑在也这里已经写了，可以返回头看看 https://mp.weixin.qq.com/s/nTB41DvE7bfrT7_rW_gfXw，用长图的形式以及讲的非常明白了。

层次遍历在「树-自顶向下」的类别中运用的比较多，相比较于递归解法，利用层次遍历更加容易理解，而且代码框架比较单一，具体的介绍和案例会在下一篇《讲透树 | 自顶向下类别题目专题》中进行介绍。

本文的非递归遍历主要针对的是层次遍历。那为什么之前讲的比较明白了，这里又会说呢？

是这样，之前讲解的层次遍历，咱们打印出来的形式和 LeetCode 题目中打印出来的形式是有些区别的。而且仅仅因为打印的区别，会引出不一样的一个思路，后面很多情况都会遇到这样的思维方式。

如下：

# 经典层次遍历打印形式
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']
# LeetCode 中打印的形式
[['A'], ['B', 'C', 'D'], ['E', 'F', 'G', 'H', 'I']]

是的，LeetCode 中打印的形式是要求将每一层的结点元素单独放到一个 list 中，最后再放置到一个大的 list 中。

传统层次遍历打印形式

先来简单回顾一下，传统的打印方式。

跟着上述图中的描述，动手画一下就会明白特别的简单。

一句话总结就是：

循环判断队列 queue 中是否有元素，如果有，访问该元素并且判断该结点元素是否有孩子结点，如果有，孩子结点依次入队 queue，否则，继续循环执行。

看代码：

while queue:
    node = queue.pop()
    res.append(node.val)
    if node.left:
        queue.appendleft(node.left)
    if node.right:
        queue.appendleft(node.right)

就是不断判断队列中队首是够有元素，如果有元素，访问该结点元素，并且判断该结点是否有孩子结点，如果有，则依次入队。继续循环判断。

其实N叉树来说的话，也是一样的逻辑，只不过是把二叉树中的两个孩子，换为N个孩子，进行入队操作。

while queue:
    node = queue.pop()
    res.append(node.val)
    for child_node in node.children:
      	queue.appendleft(child_node)

一样的道理！是不是比较简单。

LeetCode 中题目打印方式

也是用一幅图来描述，相较于经典的层次遍历，每层单独存放会稍微复杂一些，需要变换一点点思路。

核心一句话

queue 中存放的是当前层的结点集，level_queue 存放的下一层的结点集合。

每次循环遍历当前层queue中结点的同时，将该层结点集写进一个临时list，将下一层的结点入队到 level_queue 中。之后将 level_queue 赋值给 queue，循环执行，直到 queue 为空。

最后，将每层临时 list 写到一个大的 list 中

「点击下图查看高清原图」

本文链接：https://www.cnblogs.com/yydsxiaozhu/p/15056790.html

讲透树2 | 树的遍历复盘专题

1 前言

2 分类

3 递归遍历

4 非递归遍历

传统层次遍历打印形式

LeetCode 中题目打印方式

讲透树2 | 树的遍历复盘专题的更多相关文章

随机推荐

热门专题

目录导航