本文讲述了python基础编程100例：第57期-基础结构：二叉树 后序遍历！具有很好的参考价值，希望对大家有所帮助。一起跟随六星小编过来看看吧，具体如下:

第57期-基础结构：二叉树 后序遍历

1 问题描述

给定一个二叉树的根节点 root ，返回它的 后序 遍历。

后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点。即： 若二叉树为空则结束返回，否则：

（1）后序遍历左子树

（2）后序遍历右子树

（3）访问根结点 。

如图所示二叉树，后序遍历结果：DEBFCA

给你二叉树的根节点 root ，返回它节点值的后序遍历。

示例 1:

输入: root = [1,None,2,3]

输出: [3,2,1]

示例 2:

输入: root = []

输出: []

示例 3:

输入: root = [1]

输出: [1]

示例 4:

输入: root = [1,2]

输出: [2,1]

示例 5:

输入: root = [1,None,2]

输出: [2,1]

初始代码

from typing import List

class TreeNode:

    def __init__(self, x):

        self.val = x

        self.left = None

        self.right = None

def list_to_binarytree(nums):

    if nums==[]:return 

    b=root=TreeNode(nums[0])

    a=[]

    i=1

    while i < len(nums):

        if nums[i]:

            root.left=TreeNode(nums[i])

            a.append(root.left)

        if i+1<len(nums):

            if nums[i+1]:

                root.right=TreeNode(nums[i+1])

                a.append(root.right)

        i+=2

        root=a.pop(0)

    return b

root = list_to_binarytree([1,None,2,3,None,4,5,6,7,8])

class Solution:

    def postorderTraversal(self, root: TreeNode) -> List[int]:

        #在此填写代码

print(Solution().postorderTraversal(list_to_binarytree([1,None,2,3])))

print(Solution().postorderTraversal(list_to_binarytree([])))

print(Solution().postorderTraversal(list_to_binarytree([1])))

print(Solution().postorderTraversal(list_to_binarytree([1,2])))

print(Solution().postorderTraversal(list_to_binarytree([1,None,2])))

2 解题思路

按照访问左子树——右子树——根节点的方式遍历这棵树。

整个遍历过程天然具有递归的性质，我们可以直接用递归函数来模拟这一过程。

可以使用列表来存储根节点，直到访问到最左的节点，再从列表中回到上一个根节点，继续访问右节点，再对右节点进行后序遍历

3 解题方法

from typing import List

class TreeNode:

    def __init__(self, x):

        self.val = x

        self.left = None

        self.right = None

def list_to_binarytree(nums):

    if nums==[]:return 

    b=root=TreeNode(nums[0])

    a=[]

    i=1

    while i < len(nums):

        if nums[i]:

            root.left=TreeNode(nums[i])

            a.append(root.left)

        if i+1<len(nums):

            if nums[i+1]:

                root.right=TreeNode(nums[i+1])

                a.append(root.right)

        i+=2

        root=a.pop(0)

    return b

class Solution:

    def postorderTraversal(self, root: TreeNode) -> List[int]:

        stark,x=[],[]

        def a(stark,root,x):

            if root:

                stark.append(root)

            else:return []

            if root.left:a(stark,root.left,x)

            if root.right:a(stark,root.right,x)

            x.append(stark.pop().val)

            return x

        return a(stark,root,x)

print(Solution().postorderTraversal(list_to_binarytree([1,None,2,3])))

print(Solution().postorderTraversal(list_to_binarytree([])))

print(Solution().postorderTraversal(list_to_binarytree([1])))

print(Solution().postorderTraversal(list_to_binarytree([1,2])))

print(Solution().postorderTraversal(list_to_binarytree([1,None,2])))

第1-26，38-42行： 题目中已经给出的信息，运行代码时要根据这些代码进行编辑（具体为创建二叉树以及列表、二叉树转换）

第27行： 定义列表stark和x分别存放根节点与后序遍历结果

第28行： 创建函数a，用于进行后序遍历并将结果存放于x中，内部自变量stark，root以及x

第29-30行： 当root不为None时，将root存放于stark中

第31行： 当root不存在时，直接返回空列表

第32行： 当root的左节点不为None时，对root的左节点进行后序遍历（此时会一直进行左节点遍历知道左节点不存在

第33行： 当root的右节点不为None时，对root的左节点进行后序遍历

第34行： 当root的左右节点都遍历完成时（或者左右都为None时），在x中存放root节点的val值并从stark中删除该节点

第35行： 返回x列表作为后序遍历的结果

第36行： 执行函数a返回后序遍历的结果

代码运行结果为：

结构讲解

这里用到了基础结构：二叉树，简单讲解下这个二叉树：

链表

二叉树（Binary tree）是树形结构的一个重要类型。

许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。

二叉树特点是每个结点最多只能有两棵子树，且有左右之分。

结点：包含一个数据元素及若干指向子树分支的信息

结点的度：一个结点拥有子树的数目称为结点的度

叶子结点：也称为终端结点，没有子树的结点或者度为零的结点

分支结点：也称为非终端结点，度不为零的结点称为非终端结点

树的度：树中所有结点的度的最大值

结点的层次：从根结点开始，假设根结点为第1层，根结点的子节点为第2层，依此类推，如果某一个结点位于第L层，则其子节点位于第L+1层

树的深度：也称为树的高度，树中所有结点的层次最大值称为树的深度

有序树：如果树中各棵子树的次序是有先后次序，则称该树为有序树

序树：如果树中各棵子树的次序没有先后次序，则称该树为无序树

森林：由m（m≥0）棵互不相交的树构成一片森林。如果把一棵非空的树的根结点删除，则该树就变成了一片森林，森林中的树由原来根结点的各棵子树构成

更多相关技术内容咨询欢迎前往并持续关注六星社区了解详情。

想高效系统的学习Python编程语言，推荐大家关注一个微信公众号：Python编程学习圈。每天分享行业资讯、技术干货供大家阅读，关注即可免费领取整套Python入门到进阶的学习资料以及教程，感兴趣的小伙伴赶紧行动起来吧。