1. 问题的描述
给你二叉树的根节点 root ,返回它节点值的 前序 遍历。
前序遍历首先访问根结点然后遍历左子树,最后遍历右子树。在遍历左、右子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树。若二叉树为空则结束返回,否则:
(1)访问根结点。
(2)前序遍历左子树。
(3)前序遍历右子树 。需要注意的是:遍历左右子树时仍然采用前序遍历方法。
![image.jpg 基础结构:二叉树 前序遍历_结点](//dev-img.mos.moduyun.com/20231020/3b412a7d-b32e-4084-ba83-04562470a35f.png)
如图所示二叉树,前序遍历结果:ABDECF
给你二叉树的根节点 root ,返回它节点值的前序遍历。
示例 1:
![image.jpg 基础结构:二叉树 前序遍历_结点_02](//dev-img.mos.moduyun.com/20231020/1eb62d4d-bbcf-45af-b6fd-602b3ad71e44.png)
输入: root = [1,None,2,3]
输出: [1,2,3]
示例 2:
输入: root = []
输出: []
示例 3:
输入: root = [1]
输出: [1]
示例 4:
![image.jpg 基础结构:二叉树 前序遍历_结点_03](//dev-img.mos.moduyun.com/20231020/4dc355bd-1c68-4c9c-a402-444e897b0d87.png)
输入: root = [1,2]
输出: [1,2]
示例 5:
![image.jpg 基础结构:二叉树 前序遍历_二叉树_04](//dev-img.mos.moduyun.com/20231020/8127ddc2-224b-4c6a-84b5-24f3966200ad.png)
输入: root = [1,None,2]
输出: [1,2]
初始代码
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 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 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 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行: 返回二叉树的前序遍历结果
代码运行结果为:
![image.jpg 基础结构:二叉树 前序遍历_二叉树_05](//dev-img.mos.moduyun.com/20231020/f51c4b41-e475-4249-a11e-6df87d61c3f3.png)
4. 结构讲解
这里用到了基础结构:二叉树,简单讲解下这个二叉树:
链表
二叉树(Binary tree)是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,因此二叉树显得特别重要。
![image.jpg 基础结构:二叉树 前序遍历_二叉树_06](//dev-img.mos.moduyun.com/20231020/f70247a4-551f-43ff-ba4a-9a545cf46405.png)
二叉树特点是每个结点最多只能有两棵子树,且有左右之分。
结点:包含一个数据元素及若干指向子树分支的信息
结点的度:一个结点拥有子树的数目称为结点的度
叶子结点:也称为终端结点,没有子树的结点或者度为零的结点
分支结点:也称为非终端结点,度不为零的结点称为非终端结点
树的度:树中所有结点的度的最大值
结点的层次:从根结点开始,假设根结点为第1层,根结点的子节点为第2层,依此类推,如果某一个结点位于第L层,则其子节点位于第L+1层
树的深度:也称为树的高度,树中所有结点的层次最大值称为树的深度
有序树:如果树中各棵子树的次序是有先后次序,则称该树为有序树
序树:如果树中各棵子树的次序没有先后次序,则称该树为无序树
森林:由m(m≥0)棵互不相交的树构成一片森林。如果把一棵非空的树的根结点删除,则该树就变成了一片森林,森林中的树由原来根结点的各棵子树构成