Python 应用之基础结构：二叉树前序遍历

2022 年 10 月 08 日
四川
本文字数：2349 字
阅读完需：约 8 分钟

1. 问题的描述

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

前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。若二叉树为空则结束返回，否则：
（1）访问根结点。
（2）前序遍历左子树。
（3）前序遍历右子树。需要注意的是：遍历左右子树时仍然采用前序遍历方法。

如图所示二叉树，前序遍历结果：ABDECF

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

示例 1:

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

示例 2:

输入: root = []
输出: []

示例 3:

输入: root = [1]
输出: [1]

示例 4:

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

示例 5:

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

初始代码

from typing import Listclass 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 preorderTraversal(self, root: TreeNode) -> List[int]:        #在此填写代码
print(Solution().preorderTraversal(list_to_binarytree([1,None,2,3])))print(Solution().preorderTraversal(list_to_binarytree([])))print(Solution().preorderTraversal(list_to_binarytree([1])))print(Solution().preorderTraversal(list_to_binarytree([1,2])))print(Solution().preorderTraversal(list_to_binarytree([1,None,2])))

复制代码

2. 解题思路

按照访问根节点——左子树——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候，我们按照同样的方式遍历，直到遍历完整棵树。
因此整个遍历过程天然具有递归的性质，我们可以直接用递归函数来模拟这一过程。
按照定义，我们只要首先将 root 节点的值加入答案，然后调用递归来遍历 root 节点的左子树，最后调用递归来遍历 root 节点的右子树即可，递归终止的条件为碰到空节点。

3. 解题方法

from typing import Listclass 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 preorderTraversal(self, root: TreeNode) -> List[int]:        def a(x,root):            if root:                x.append(root.val)                a(x,root.left)                a(x,root.right)            return x        x=[]        return a(x,root)
print(Solution().preorderTraversal(list_to_binarytree([1,None,2,3])))print(Solution().preorderTraversal(list_to_binarytree([])))print(Solution().preorderTraversal(list_to_binarytree([1])))print(Solution().preorderTraversal(list_to_binarytree([1,2])))print(Solution().preorderTraversal(list_to_binarytree([1,None,2])))

复制代码

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

第 27 行： 定义函数 a 用于递归，内部变量 root 二叉树以及 x 列表来存放二叉树的节点

第 28 行： 当二叉树节点存在时执行 if 内部操作

第 29 行： x 列表中存放 root 二叉树节点的值

第 30 行： 递归操作，开始遍历二叉树的左子树，再对此左子树进行前序遍历操作

第 31 行： 递归操作，当左子树遍历完成时，开始遍历二叉树的右子树，再对此右子树进行前序遍历操作

第 32 行： 当根节点 root 的右子树遍历完成，结束遍历并返回列表 x

第 33 行： 定义 x 为空列表

第 34 行： 返回二叉树的前序遍历结果

代码运行结果为：

4. 结构讲解

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

链表

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

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

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

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

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

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

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

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

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

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

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

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

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/2dc996494e2c18ff2835436c7】。文章转载请联系作者。

向阳逐梦

关注

人生享受编程，编程造就人生！ 2022.06.01 加入

InfoQ签约作者、阿里云“乘风者计划”签约博主

发布

暂无评论

创作场景

Python 应用之基础结构：二叉树 前序遍历