# 第56期-基础结构：二叉树中序遍历

Python是一门需要不断实践练习的编程语言，本文档将AI大学堂学员交流群的Python每周练习进行汇总，希望各位小伙伴能够多进行实践练习，逐渐爱上这门神奇的编程语言，掌握它并在生活中能够使用它。

# 1 问题描述

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

中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。若二叉树为空则结束返回，否则：
（1）中序遍历左子树
（2）访问根结点
（3）中序遍历右子树。

如图所示二叉树，中序遍历结果：DBEAFC

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

示例 1:

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

示例 2:

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

示例 3:

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

示例 4:

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

示例 5:

输入: 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 inorderTraversal(self, root: TreeNode) -> List[int]:
        #在此填写代码

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

# 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 inorderTraversal(self, root: TreeNode) -> List[int]:
        stack,mid=[],[]
        while root or stack:
            while root:
                stack.append(root)
                root=root.left
            root=stack.pop()
            mid.append(root.val)
            root=root.right
        return mid

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

第1-26，37-41行： 题目中已经给出的信息，运行代码时要根据这些代码进行编辑（具体为创建二叉树以及列表、二叉树转换）
第27行： 定义列表stark和mid分别存放根节点与后序遍历结果
第28行： 当root不为None或者stark不为空时，执行循环
第29行： 当root不为None时，执行循环
第30行： 在stark列表中存放root节点
第31行： 遍历root的左节点
第32行： 当root为None时，说明左节点已经到头，返回root节点为最后没有左子树的节点，并在stark列表中删除该节点
第33行： 在mid列表中加入root节点的val值
第34行： 对root的右子树进行中序遍历
第34行： 返回mid列表作为中序遍历的结果

代码运行结果为：

# 结构讲解

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

二叉树特点是每个结点最多只能有两棵子树，且有左右之分。
结点：包含一个数据元素及若干指向子树分支的信息
结点的度：一个结点拥有子树的数目称为结点的度
叶子结点：也称为终端结点，没有子树的结点或者度为零的结点
分支结点：也称为非终端结点，度不为零的结点称为非终端结点
树的度：树中所有结点的度的最大值
结点的层次：从根结点开始，假设根结点为第1层，根结点的子节点为第2层，依此类推，如果某一个结点位于第L层，则其子节点位于第L+1层
树的深度：也称为树的高度，树中所有结点的层次最大值称为树的深度
有序树：如果树中各棵子树的次序是有先后次序，则称该树为有序树
序树：如果树中各棵子树的次序没有先后次序，则称该树为无序树
森林：由m（m≥0）棵互不相交的树构成一片森林。如果把一棵非空的树的根结点删除，则该树就变成了一片森林，森林中的树由原来根结点的各棵子树构成

# 4 视频解析

高清视频讲解，请查看AI大学堂Python基础实战100例 (opens new window)
关注『讯飞AI大学堂』公众号，发送 python100 即可领取Python基础实战100例源代码
AI大学堂公众号.png