写点什么

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
用户头像

向阳逐梦

关注

人生享受编程,编程造就人生! 2022.06.01 加入

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

评论

发布
暂无评论
Python应用之基础结构:二叉树 前序遍历_二叉树_向阳逐梦_InfoQ写作社区