2023年6月22日发(作者：)

测试开发基础之算法（11）：⼆叉树的三种遍历算法及典型题解树是⼀种⾮线性表数据结构，相⽐数组、链表、队列、栈、散列表等线性数据结构要复杂⼀些。树根据存储的数据特点，形成了很多有特点的树，⽐如典型的⼆叉树，在很多场景具有应⽤。⼆叉树在⾯试中也是经常会被考到的点。本篇⽂章就来全⾯认识⼆叉树，并学会在⼆叉树的各种操作。1.树和⼆叉树的核⼼概念⽤图来展⽰树的概念，最为直观，下⾯5幅图中第⼀个不是树，其余四个是树。树这种数据结构很像现实⽣活中的树。图中的每个点，叫做“节点”，节点之间的连线叫做“⽗⼦关系”。以上⾯的第②个图为例，A叫根节点，A是B的⽗节点，B是A的⼦节点，B、C、D之间互称兄弟节点。G H I叫作叶⼦节点。“树”还有三个⽐较相似的概念：⾼度（Height）、深度（Depth）、层（Level），上⾯第三幅图展⽰了三者之间的区别。树的结构很多，但是常⽤的还是⼆叉树。⼆叉树顾名思义是只有两个叉，也就是有左右两个节点，如上⾯的③④⑤都是⼆叉树，⽽②是三叉树。上图第④幅图，除了叶⼦节点，其他节点都有两个⼦节点，这样的数叫做满⼆叉树。上图的第⑤幅图，叶⼦节点都落在最下⾯两层，最后⼀层的叶⼦节点都靠左排列，其它层节点的个数都达到了最⼤个数，这样的数叫做完全⼆叉树。2.⼆叉树的存储⽅式满⼆叉树的特点⽐较明显，但是完全⼆叉树的特点并不明显，为啥会特别提出完全⼆叉树的概念呢。这主要与⼆叉树的存储⽅式相关，完全⼆叉树的数组储存⽅式最省空间。下⾯我们详细看下⼆叉树的存储⽅式。⼆叉树有两种常⽤的存储⽅式：⼆叉链式存储法和数组顺序存储法。⼆叉链式存储⼆叉链式存储是⽐较直观、常⽤和简单的存储法。如下图树中的每⼀个字段都有三个字段，分别是数据，左⼦节点指针和右⼦节点指针。从根节点开始，使⽤左右⼦节点指针，就可以遍历整个树了。数组的顺序存储法基于数组的顺序存储法，是将树中的所有结点存放到数组中。根节点存放到数组下标i=1的位置，左⼦节点存放到下标为2i的位置，右⼦节点存放下标为2i+1的位置。以下图完全⼆叉树为例：可以见完全⼆叉树在数组中的存储⽅式⽐较紧凑，仅浪费了⼀个下标为0的空间。⽽⾮完全⼆叉树，采⽤数字的顺序存储法则会浪费⽐较多的空间。3.前中后序遍历⼆叉树遍历是⼆叉树的重要操作，⽐较经典的遍历⽅法有：前序遍历、中序遍历和后续遍历。前中后代表是遍历时，当前节点与左右⼦节点的先后顺序。前序遍历，指的是先打印当前节点，再打印左⼦树，最后打印右⼦树。中序遍历，指的是先打印左⼦树，再打印当前节点，最后打印右⼦树。后续遍历，指的是先打印左⼦树，再打印右⼦树，最后打印当前节点。上⾯三种遍历⽅式，⽤图来表⽰就是：实际上，⼆叉树的遍历就是⼀个递归过程。⽐如前序遍历，就是先打印当前节点，接着递归打印左⼦树，最后递归打印右⼦树，遍历的时间复杂度是 O(n)。前序遍历的递推公式：preOrder (node) = print node->preOrder(node->left)->preOrder(node->right)中序遍历的递推公式：inOrder(node) = inOrder(node->left)->print node->inOrder(node->right)后序遍历的递推公式：postOrder(node) = postOrder(node->left)->postOrder(node->right)->print node有了递归公式，我们看看代码的实现。from typing import TypeVar, Generic, Optional, GeneratorT = TypeVar("T")class TreeNode(Generic[T]): def __init__(self, value): = value = None = Nonedef pre_order(root: Optional[TreeNode[T]]) -> Generator[T, None, None]: """ :param root:根节点 :return:⽣成器 """ if root: yield #

先打印当前节点 yield from pre_order() #

再打印左⼦树 yield from pre_order() #

再打印右⼦树def in_order(root: Optional[TreeNode[T]]) -> Generator[T, None, None]: if root: yield from in_order() yield yield yield from in_order()def post_order(root: Optional[TreeNode[T]]) -> Generator[T, None, None]: if root: yield from post_order() yield from post_order() yield f __name__ == '__main__': b_tree = TreeNode("root_node") second_layer_left = TreeNode("second_layer_left") second_layer_right = TreeNode("second_layer_right") first = TreeNode("first") second = TreeNode("second") third = TreeNode("third") fourth = TreeNode("fourth") fifth = TreeNode("fifth") sixth = TreeNode("sixth") #

拼接成树 b_ = second_layer_left b_ = second_layer_right second_layer_ = first second_layer_ = second second_layer_ = third second_layer_ = fourth = fifth = sixth #

前序遍历 print(list(pre_order(b_tree))) #

中序遍历 print(list(in_order(b_tree))) #

后续遍历 print(list(post_order(b_tree)))4.按层遍历⼆叉树按层次遍历⼆叉树，就是即逐层地从左到右访问所有节点。例如：给定⼆叉树: [3,9,20,null,null,15,7], 3 / 9 20 / 15 7返回其层次遍历结果：[ [3], [9,20], [15,7]]def layer_order(root: Optional[TreeNode[T]]) -> list: layers = [] #

输出结果列表 def layer_order_dfs(node, layer): if not node: #

递归终⽌条件 return layers #

处理当前层 if len(layers) <= layer: #

当前节点所在层⼤于等于输出列表长度时，给当前节点所在层新创建⼀个列表 ([]) layers[layer].append() #

当前节点加⼊当前层的列表中 #

递归处理下⼀层 layer_order_dfs(, layer + 1) layer_order_dfs(, layer + 1) layer_order_dfs(root, 0) #

从第1层开始处理 return layers5.练习题：求⼆叉树最⼤最⼩深度本⽂的第⼀⼩节介绍了树的⾼度和深度概念，它们都是从0开始计数，只是⾼度从叶⼦节点层开始计数，深度从根节点所在层开始计数。题⽬要求的最⼤深度表⽰从根节点到最近叶⼦节点的最长路径上的节点数量。题⽬要求的最⼩深度表⽰从根节点到最近叶⼦节点的最短路径上的节点数量。每个节点的深度与它左右⼦树的深度有关，且最⼤深度等于其左右⼦树最⼤深度值加上 1。⽤递归公式表⽰，可以写作：max_depth(node) = max(max_depth(), max_depth()) + 1当输⼊的节点为空节点时，我们⽆需继续计算其⼦树的深度，此时可以直接结束递归函数，并返回空节点的深度为 0。因此递归的终⽌条件是： if node is None: return 0有了递归公式，和终⽌条件，代码就⽐较容易写了：def max_depth(node: Optional[TreeNode[T]]) -> int: if node is None: #

当输⼊的节点为空节点时，我们⽆需继续计算其⼦树的深度，直接返回0，结束递归函数 return 0 if is None: #

当前节点不为空，但是右⼦树为空，直接返回左⼦树的最⼤深度 return max_depth() + 1 if is None: #

当前结点不为空，右⼦树不为空，但是左⼦树为空，直接返回右⼦树的最⼤深度 return max_depth() + 1 #

当前节点不为空，左右⼦节点也不为空，返回左右⼦树最⼤深度 return max(max_depth(), max_depth()) + 1

与求最⼤深度类似，求最⼩深度也可以采⽤递归办法。直接上代码：def min_depth(node: Optional[TreeNode[T]]) -> int: if node is None: return 0 if is None: return min_depth() + 1 if is None: return min_depth() + 1 return min(min_depth(), min_depth()) + 1因为每个节点都需要被访问⼀次，因此时间复杂度为 O(n)。对于空间复杂度，主要考虑到递归时调⽤栈的空间情况。最坏情况：树完全不平衡。例如每个节点都只有右节点或者左节点，此时将递归 n 次，需要保持调⽤栈的存储为 O(n)。最好情况：树完全平衡。即树的⾼度为 log(n)，此时空间复杂度为 O(log(n))