二叉树的四种遍历

二叉树的四种遍历

二叉树

二叉树是一种数据结构,简单来说就是一个包含节点,以及它的左右孩子的一种数据结构。

二叉树

遍历方式

如果对每一个节点进行编号,你会以什么方式去遍历每个节点呢?

二叉树

如果你按照根节点->左孩子->右孩子的方式进行遍历,即先序遍历,每次先遍历根节点,遍历结果为1,2,3,4,5,6,7

同理如果你按照左孩子->根节点->右孩子的方式遍历,即中序遍历,遍历结果为2,5,1,6,3,7

如果你按照左孩子->右孩子->根节点的方式遍历,即后序遍历,遍历结果为4,5,2,6,7,3,1

最后,层次遍历就是按照每一层从左享有的方式进行遍历,遍历结果就是1,2,3,4,5,6,7

题目解析

给定一个二叉树,让我们使用一个数组来返回遍历结果。

递归解法

由于层次遍历的递归解法不是主流,因此只介绍前三种递归解法。他们的模板相对比较固定,一般都会新增一个dfs函数

def dfs(root):
    if not root:
        return
        res.append(root.val)# 前序遍历
        dfs(root.left)
        dfs(root.right)

对于前序、中序和后序遍历,只需要将递归函数里面的res.append(root.val)放在不同位置即可,然后调用这个递归函数就可以了,代码完全一样。

  1. 前序遍历

    class solution:
        def preorderTravelsal(self,root:TreeNode)->List[int]:
            res = []
            def dfs(root):
                nonlocal res# 为了让上一级定义的res可以在这个函数中用
                if not root:
                    return
                res.append(root.val)
                dfs(root.left)
                dfs(root.right)
             dfs(root)
             return res
    
  2. 中序遍历

    class solution:
        def preorderTravelsal(self,root:TreeNode)->List[int]:
            res = []
            def dfs(root):
                nonlocal res
                if not root:
                    return
                dfs(root.left)
                res.append(root.val)
                dfs(root.right)
             dfs(root)
             return res
    
  3. 后序遍历

    class solution:
        def preorderTravelsal(self,root:TreeNode)->List[int]:
            res = []
            def dfs(root):
                nonlocal res
                if not root:
                    return
                dfs(root.left)
                dfs(root.right)
                res.append(root.val)             dfs(root)
             return res
    

一样的代码,稍微调用一下位置就可以,如此固定的套路,使得只掌握递归解法并不足以令别人信服,因此我们有必要掌握迭代解法,同时也会加深我们对数据结构的理解。

迭代解法

  1. 前序遍历

    常规解法:

    使用栈来进行迭代,过程如下:

    • 初始化栈,并将根节点入栈;
    • 当栈不为空时:
    • 弹出栈顶元素node,并将值添加到结果中;
    • 如果node的右子树非空,将右子树入栈;
    • 如果node的左子树非空,将左子树入栈;
      由于栈是先进先出的顺序,所以入栈时先将右子树入栈,这样使得前序遍历结果为"根->左->右"的顺序。
    class solution:
        def preorderTravel(self,root:TreeNode)->List[int]:
            if not root :return []
            stack,res=[root],[]
            while stack:
                node = stack.pop()
                if node:
                    res.append(node.val)
                    if node.right:
                        stack.append(node.right)
                    if node.left:
                        stack.append(node.left)
            return res
    

    模板解法:

    你也可以直接启动“僵尸”模式,套用迭代的模板来一波“真香操作”。

    模板解法的思路稍有不同,他先将根节点cur和所有的左孩子入栈并加入结果中,直至cur为空,用一个循环实现:

模板解法

然后每弹出一个栈顶元素tmp,就到达它的右孩子,再将这个节点当做cur重新按照上面的步骤来一遍,直至栈为空。这里又需要一个while循环。

class solution:
    def preorderTraversal(self,root:TreeNode)->List[int]:
        if not root:return []
        cur,stack,res = root,[],[]
        while cur or stack:
            while cur:# 根节点和左孩子入栈
                res.append(cur.val)
                stack.append(cur)
                cur = cur.left
            tmp = stack.pop()# 每弹出一个元素,就到达右孩子
            cur = tmp.right
        return res
  1. 中序遍历

    和前序遍历的代码完全相同,只是在出栈的时候才将节点tmp的值加入到结果中。

    模板解法

    class solution:
        def inorderTraversal(self,root:TreeNode)->List[int]:
            if not root:return[]
            cur,stack,res = root,[],[]
            while cur or stack:
                while cur:# 入栈并到达最左端的叶子节点
                    stack.append(cur)
                    cur = cur.left
                tmp = stack.pop()
                res.append(tmp.val)# 出栈时再加入结果
                cur = tmp.right
            return res
    
  2. 后序遍历

    模板解法

    继续按照上面的思想,这次我们反着思考,节点先到达最右端的叶子节点并将路径上的节点入栈;

    然后每次从栈中弹出一个元素后,cur到达它的左孩子,并将左孩子看做cur继续执行上面的步骤。

    最后将结果反向输出即可。参考代码如下:

    class solution:
        def postorderTraversal(self,root:TreeNode)->List[int]:
            if not root:return []
            cur,stack,res = root,[],[]
            while cur or stakck:
                while cur:
                    res.append(cur.val)
                    stack.append(cur)
                    cur = cur.right
                tmp = stack.pop()
                cur = tmp.left
            return res[::-1]
    

    然而,后序遍历采用模板解法并没有按照真实的栈操作,而是利用了结果的特点反向输出,不免显得技术含量不足。

    因此掌握标准的栈操作解法是必要的。

    常规解法:

    类比前序遍历的常规解法,我们只需要将输出的“根->左->右”的顺序改为“左->右->根”就可以了。

    如何实现呢?这里有一个小技巧,我们入栈时额外加入一个标识,比如这里使用flag=0;

后序遍历栈解法

每次从栈中弹出元素时,如果flag为0,则需要将flag变为1并连同该节点再次入栈,只有当flag为1时才可以将该节点加入到结果中。

```python
class solution:
    def postorderTraversal(self,root:TreeNode)->List[int]:
        if not root :return[]
        stack,res = [(0,root)],[]
        while stack:
            flag,node = stack.pop()
            if not node:continue
            if flag ==1:# 遍历过了的话,就加入到结果
                res.append(node.val)
            else:
                stack.append((1,node))
                stack.append((0,node.right))# 右
                stack.append((0,node.left))# 左
        return res
```
  1. 层次遍历

    二叉树的层次遍历的迭代方法与前面不同,因为前面的都采用了深度优先搜索的方式,而层次遍历使用了广度优先搜索,广度优先搜索主要使用了队列实现,也就不能使用前面的模板解法了。

    广度优先搜索的步骤为:

    • 初始化队列q,并将根节点root加入到队列中;
    • 当队列不为空时:
    • 队列中弹出节点node,加入到结果中
    • 如果左子树非空,左子树加入队列;
    • 如果右子树非空,右子树加入队列;

    由于题目要求每一层保存在一个子数组中,所以我们额外加入了level保存每层的遍历结果,并使用for循环来实现。

层次遍历
class solution:
    def levelorder(self,root:TreeNode)->List[List[int]]:
        if not root: return []
        res,q = [],[root]
        while q:
            n = len(q)
            level = []
            for i in range(n):
                node = q.pop(0) # 这里的q相当于一个队列
                level.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            res.append(level)
        return res

总结

总结一下,在二叉树的前序、中序、后序遍历中,递归实现的伪代码为:

边界条件
定义 dfs 函数:
    如果root为空,返回;
    递归左子树 # 顺序可变
    递归右子树
    root的值加入到结果
执行递归函数,返回结果

迭代实现的伪代码为:

边界条件
初始化 cur,stack,root
while stack or cur非空:
    while 循环:
        cur 向左下或者右下遍历
        cur 的值入栈
    弹出节点tmp
    cur回到tmp的左或者右子树
返回结果
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 216,651评论 6 501
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 92,468评论 3 392
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 162,931评论 0 353
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 58,218评论 1 292
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 67,234评论 6 388
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,198评论 1 299
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,084评论 3 418
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,926评论 0 274
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,341评论 1 311
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,563评论 2 333
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,731评论 1 348
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,430评论 5 343
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 41,036评论 3 326
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,676评论 0 22
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,829评论 1 269
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,743评论 2 368
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,629评论 2 354

推荐阅读更多精彩内容