树数据结构-力扣刷树题需要知道的（Python）
2019-05-24 本文已影响0人
玖月晴
树是一种重要的数据结构，而二叉树是其中的重点和难点，有关二叉树的基础知识，读者可移步【二叉树基础】查看更多内容。这里，我们重点讲述树的基本结构在python中是如何构建和应用的。
1. 二叉树的结点
二叉树的结点有三个实例变量：
- 结点值，可以是任意数据类型，但是以整数最为简单；
- 左孩子，为二叉树节点，如果没有则设置为None。
- 右孩子，为二叉树节点，如果没有则设置为None。
每个结点在实例化时，都需要设置该结点的值，并且该结点默认左右孩子均为None，需要通过赋值语句进行添加。
class TreeNode:
"""
二叉树的结点
"""
def __init__(self, x):
self.val = x # 结点值
self.left = None # 左孩子
self.right = None # 右孩子
2. 二叉树的构建
这里，我们设计一个函数，通过一个列表构建一棵二叉树，输入的列表按照二叉树的层次顺序给出各个元素，我们根据二叉树的下标寻找结点之间的对应关系：下标为i的结点的左右孩子在列表中的下标分别是2i+1和2i+2。
def create_tree(nodes):
"""
根据列表构建一棵二叉树
:param nodes: 层次遍历序列
:return: 二叉树的根节点
"""
def helper(node, i): # 用列表递归创建二叉树，
if i < len(nodes): # 当下标索引满足条件时
if nodes[i] in ['#', None]: # 如果列表中下标为i的结点为空
return None # 返回None
else:
node = TreeNode(nodes[i]) # 构建当前结点
node.left = helper(node.left, 2 * i + 1) # 构建左子树，通过下标查找
node.right = helper(node.right, 2 * i + 2) # 构建右子树，通过下标查找
return node # 返回根节点为下标为i的元素的子树
return node # 返回根节点
root = TreeNode(0) # 临时结点
root = helper(root, 0) # 建立树
return root # 返回树的根节点
假设我们要构建一棵满二叉树：
1
/ \
2 3
/ \ / \
4 5 6 7
我们只需要调用该函数即可：
root = create_binary_tree([1, 2, 3, 4, 5, 6, 7])
如果我们需要构建一棵普通二叉树，例如：
1
/ \
2 3
/ /
4 6
我们将为空的叶子结点填充为None或“#”，最后一层的最后几个结点如果为连续的空结点，可以不做操作。
root = create_binary_tree([1, 2, 3, 4, None, 6])
3. 二叉树的遍历
二叉树常见的遍历方式有四种，前序遍历、中序遍历、后序遍历以及层次遍历，有关遍历顺序的基础知识可以参考【二叉树的遍历】，每一种遍历又可以通过递归和迭代两种方式实现。
举个栗子，对于一棵满二叉树，我们分别使用前序、中序、后序和层序打印方式，结果为：
1
/ \
2 3
/ \ / \
4 5 6 7
前序：[1, 2, 4, 5, 3, 6, 7]
中序：[4, 2, 5, 1, 6, 3, 7]
后序：[4, 5, 2, 6, 7, 3, 1]
层序：[1, 2, 3, 4, 5, 6, 7]
递归实现
遍历的递归实现要更简洁易懂一些，无需借助栈、队列等额外数据结构，前序、中序和后序的遍历顺序有十分类似的实现方式，唯一的区别在于根节点与左右孩子之间的顺序关系：
-
如果输入空树，直接返回空列表；
-
如果输入不是空树，获得当前结点的值并存放在列表中，递归调用本函数获得左子树和右子树的遍历结果：
（1）前序遍历：根节点+左子树+右子树；
（2）中序遍历：左子树+根节点+右子树；
（3）后序遍历：左子树+右子树+根节点。
1. 前序遍历
def pre_order(node):
"""
前序遍历
:param node: 二叉树的根节点
:return: 遍历结果列表
"""
if not node:
return []
return [node.val] + pre_order(node.left) + pre_order(node.right)
2. 中序遍历
def in_order(node):
"""
中序遍历
:param node: 二叉树的根节点
:return: 遍历结果列表
"""
if not node:
return []
return pre_order(node.left) + [node.val] + pre_order(node.right)
3. 后序遍历
def post_order(node):
"""
后序遍历
:param node: 二叉树的根节点
:return: 遍历结果列表
"""
if not node:
return []
return pre_order(node.left) + pre_order(node.right) + [node.val]
我们可以考虑把以上三种遍历方式用python中的lambda表达式进行快速定义，只需要一句话定义一个函数：
# 前序遍历
pre_order = lambda node: [node.val] + pre_order(node.left) + pre_order(node.right) if node else []
# 中序遍历
in_order = lambda node: in_order(node.left) + [node.val] + in_order(node.right) if node else []
# 后序遍历
post_order = lambda node: post_order(node.left) + post_order(node.right) + [node.val] if node else []
4. 层序遍历
我们借助列表实现层序遍历。我们将层序遍历的结果用列表嵌套结构表示，并且列表中的每个元素是每一层的遍历结果，也是列表形式。在递归调用时，我们构建助手函数（helper），用于将数中某一层的某结点添加到指定层的结果列表当中。
def level_order(root):
"""
层序遍历
:type root: TreeNode
:rtype: List[List[int]]
"""
def helper(node, level):
"""
将以node为根节点的树的层次遍历结果添加到res中
:param node: 根节点
:param level: 根节点所在的层次
:return:
"""
if not node: # 如果根节点为空
return # 跳出
else:
res[level-1].append(node.val) # 将根节点的值添加到所在层的结果列表中
if len(res) == level: # 遍历到新层时，只有最左边的结点使得等式成立
res.append([]) # 添加下一层
helper(node.left, level+1) # 遍历左孩子
helper(node.right, level+1) # 遍历右孩子
res = [[]] # 默认层序遍历结果为空列表
helper(root, 1) #
return res[:-1] # 去掉最后一层结束时添加的
迭代实现
迭代实现要比递归实现更加复杂，使用迭代法实现二叉树的遍历需要借助队列或栈等数据结构。
前序、中序和后续遍历都要用到栈的数据结构，它们有共同的循环控制条件，即当栈与当前结点均为空时跳出循环，在循环内部，针对当前结点是否为空的情况也有不同的操作：
前序遍历：当前结点不为空记录当前结点值，并把右结点入栈，更新当前结点为左孩子，当前结点为空时更新为栈顶结点；
中序遍历：当前结点不为空，则结点入栈，并更新为左孩子，当前结点为空时更新为栈顶结点，记录当前结点值并更新为右孩子；
后序遍历：当前结点不为空，则记录结点值，左孩子入栈，当前结点更新为右孩子，若节点为空则更新为栈顶结点。
1. 前序遍历
def pre_order(root):
"""
前序遍历
:param root: 二叉树的根节点
:return: 遍历结果列表
"""
stack = [] # 构造空栈
res = [] # 结果列表
cur = root # 当前结点
while stack or cur: # 如果栈和当前结点均为空时跳出循环
if cur: # 如果当前结点不为空
res.append(cur.val) # 则添加当前结点的值到结果列表中
stack.append(cur.right) # 把右子树放进栈中
cur = cur.left # 更新当前结点为左子树
else: # 如果当前结点为空
cur = stack.pop() # 从栈中弹出结点
return res # 返回结果列表
2. 中序遍历
def in_order(root):
"""
中序遍历
:param root:
:return:
"""
stack = [] # 构造空栈
res = [] # 结果列表
cur = root # 当前结点
while stack or cur: # 如果栈和当前结点均为空时跳出循环
if cur: # 如果当前结点不为空
stack.append(cur) # 首先将当前结点放入栈中
cur = cur.left # 更新当前结点为左孩子
else: # 如果当前结点为空
cur = stack.pop() # 从栈中弹出元素
res.append(cur.val) # 结果列表中添加当前结点的值
cur = cur.right # 更新当前结点为右孩子
return res # 返回结果列表
3. 后序遍历
def post_order(root):
"""
后续遍历
:param root:
:return:
"""
stack = [] # 构造空栈
res = [] # 结果列表
cur = root # 当前结点
while stack or cur: # 如果栈和当前结点均为空时跳出循环
if cur: # 如果当前结点不为空
res.append(cur.val) # 当前结点值添加到结果列表
stack.append(cur.left) # 左孩子入栈
cur = cur.right # 更新当前结点为右孩子
else: # 如果当前结点为空
cur = stack.pop() # 弹出右孩子
return res[::-1] # 结果列表逆序输出
4. 层序遍历
层次遍历需要使用队列，每次将结点出队，记录该结点值并将其左右孩子依次入队，直到队列中没有结点为止。
def level_order(root):
if not root: # 如果输入空树
return [] # 返回空列表
res = [] # 结果列表
cur = root # 当前结点
queue = [cur] # 当前结点入队
while queue: # 只要队列不为空
cur = queue.pop(0) # 元素出队
res.append(cur.val) # 添加当前结果
if cur.left: # 如果左子树不为空
queue.append(cur.left) # 左孩子入队
if cur.right: # 如果右子树不为空
queue.append(cur.right) # 右孩子入队
return res # 返回结果列表
“之”字形打印二叉树
这是二叉树的层次遍历的一种操作，和普通的层次遍历不同，我们对偶数行二叉树的层结果进行逆序即可。这里为大家提供一种便于理解的方式：
import create_binary_tree # 引入上文中提到的构建二叉树的函数，如果在同一个py文件中则不必
def get_layers(root, switch=True):
"""
按层打印二叉树
:param pRoot: 输入二叉树的根节点
:param switch: “之”字形打印开关，如果打开，则按“之”字形打印，否则每一层从左到右打印
:return: 返回结果列表，其中的每个元素也是列表，代表了每一层的结点值
"""
if not root: # 如果输入空树
return [] # 返回空列表
cur_layer = [root] # 当前层结点
result = [] # 结果列表
right2left = False # 方向标志，默认从左到右打印
while cur_layer: # 如果当前层有结点
cur_val = [] # 当前层的值
next_layer = [] # 下一层结点
for node in cur_layer: # 遍历当前层的每一个结点
cur_val.append(node.val) # 获得当前结点层的值
if node.left: # 如果左子孩子不为空
next_layer.append(node.left) # 将左孩子添加到下一层结点列表中
if node.right: # 如果右孩子不为空
next_layer.append(node.right) # 将右孩子添加到当前结点中
if right2left: # 如果要求从右到左打印
cur_val.reverse() # 将当前层结点值列表逆序
if cur_val: # 如果当前层结点值列表不为空
result.append(cur_val) # 添加到最终结果中
cur_layer = next_layer # 更新当前层为下一层列表
if switch: # 如果打开了“之”字形打印开关
right2left = not right2left # 每轮循环翻转方向标志
return result # 返回最终结果
if __name__ == "__main__":
# 测试代码
s = Solution()
r = create_binary_tree([1,2,3,4,5,6,7])
print(get_layers(r))
# 结果：[[1], [3, 2], [4, 5, 6, 7]]
这里通过不断翻转变量（right2left）的布尔值实现相邻层的打印顺序不同，并在函数开始设置开关（switch）来决定是否需要进行“之”字形打印，读者可以尝试关闭这个开关，那么实验的结果就与层次遍历无异。
4. 二叉树的序列化和反序列化
对于所有结点都是整数的二叉树，我们可以用一个字符串去代表这棵树，这个过程叫做二叉树的序列化，根据代表一棵树的字符串序列重构出这棵树的过程即为二叉树的反序列化。序列化和反序列化互为逆过程，类似二叉树的遍历与二叉树的构建互为逆过程。这里需要保持两个一致：
遍历顺序一致：如果序列化二叉树时采用前序遍历方式，则重构二叉树依旧需要依照前序遍历顺序重构；
主要字符对应：如果序列化二叉树时空结点用“#”表示，那么重构二叉树时遇到“#”时应该构造空结点。
1. 二叉树的序列化
二叉树的序列化过程使用递归很简单，我们可以采用递归前序遍历方式实现：
def serialize(root):
"""
二叉树的序列化
:param root:
:return:
"""
if not root:
return "#"
return str(root.val) + ',' + serialize(root.left) + ',' + serialize(root.right)
2. 二叉树的反序列化
与上述序列化过程类似，我们采用前序遍历方式重建二叉树。
def deserialize(s):
"""
二叉树的反序列化
:param s:
:return:
"""
def helper(nodes):
if not nodes:
return None
val = nodes.pop(0) # 取出第一个元素
if val == '#': # 如果该元素为“#”
node = None # 则当前结点为空
else: #
node = TreeNode(int(val)) # 实例化当前结点
node.left = helper(nodes) # 构建左子树
node.right = helper(nodes) # 构建右子树
return node # 返回当前结点
nodes = s.split(',') # 划分成列表
return helper(nodes) # 反序列化
5. 二叉树的属性
1. 二叉树的最大深度
从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。寻找二叉树的最大深度。
这道题在力扣中对应的题目是【题目104. 二叉树的最大深度】这里我们采用递归法和迭代法两种方式解决这个问题。递归法实际上是在获取所有结点所在层次的最大值：
def max_depth(root):
"""
递归法获得二叉树的最大深度
:param root:
:return:
"""
if not root: # 如果输入空树
return 0 # 最大深度为零
max_left = max_depth(root.left) # 获得左子树最大深度
max_right = max_depth(root.right) # 获得右子树最大深度
return max(max_left, max_right) + 1 # 左右子树的最大深度加上根节点，即为当前子树最大深度
迭代法类似层序遍历，只是这里不需要记录各层结点，只需要统计达到的层次：
def get_depth(root):
"""
获得二叉树的深度
:param root: 输入二叉树的根节点
:return: 返回二叉树的深度
"""
if not root: # 如果输入结点为空
return 0 # 则最大深度为零
cur_layer = [root] # 当前层结点列表
depth = 0 # 初始深度为零
while cur_layer: # 如果当前层存在结点，则执行
next_layer = [] # 初始化下一层结点列表
for node in cur_layer: # 遍历当前层每一个结点
if node.left: # 如果当前结点存在左孩子
next_layer.append(node.left) # 将左孩子添加到下一层结点列表
if node.right: # 如果当前结点存在右孩子
next_layer.append(node.right) # 将右孩子添加到下一层结点列表
cur_layer = next_layer # 更新当前结点列表为下一层结点列表
depth += 1 # 深度+1
return depth # 返回最大深度
测试用例：
if __name__ == "__main__":
r = create_binary_tree([1, 2, 3, 4, 5, 6, 7])
print(max_depth(r))
# 答案：3
2. 二叉树的最小深度
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。这道题来源于【111. 二叉树的最小深度】，解法与上题类似，这里，我们使用递归实现，更加便捷：
def min_depth(root):
"""
二叉树的最小深度
:param root: 二叉树的根节点
:return: 二叉树的最小深度
"""
if not root: # 如果输入空树
return 0 # 返回最小深度零
left_min_depth = min_depth(root.left) # 调用本函数获得左子树的最小深度
right_min_depth = min_depth(root.right) # 调用本函数获得右子树的最小深度
if left_min_depth > 0 and right_min_depth > 0: # 如果左右子树最小深度都不是0
res = min(left_min_depth, right_min_depth) + 1 # 当前子树的最小深度是两者较小值+1
else: # 如果有一个子树是空
res = max(left_min_depth, right_min_depth) + 1 # 当前数的最小深度取决于非空子树，其深度+1
return res
测试用例：
if __name__ == "__main__":
r = create_binary_tree([1, 2, 3, 4, 5, 6, 7])
print(min_depth(r))
# 答案：3
3. 所有路径
本题来源【257. 二叉树的所有路径】，具体解法可以查看。
def get_paths(root):
"""
找到以root为根节点的二叉树的所有路径
:type root: 根节点
:rtype: 所有路径，列表嵌套形式给出
"""
def helper(root, path, res):
"""
助手
:param root: 根节点
:param path: 遍历到root为止的当前路径
:param res: 最终结果
:return:
"""
cur_path = path + [root.val] # 当前路径
if not root.left and not root.right: # 如果输入是叶子结点
res.append(cur_path) # 把路径添加到结果
return # 返回
if root.left: # 如果存在左孩子
helper(root.left, cur_path, res) # 考虑左孩子
if root.right: # 如果存在右孩子
helper(root.right, cur_path, res) # 考虑右孩子
if not root: # 如果输入空树
return [] # 不存在路径，返回空列表
paths = [] # 最终结果
helper(root, [], paths) # 寻找路径
return paths # 返回结果
测试用例：
if __name__ == "__main__":
r = create_binary_tree([1, 2, 3, 4, 5, 6, 7])
print(min_depth(r))
# 结果：[[1, 2, 4], [1, 2, 5], [1, 3, 6], [1, 3, 7]]
4. 对称二叉树
本题源于【101. 对称二叉树】，用函数判断二叉树是否是镜像二叉树。如果左右子树镜像对称，那么二叉树也镜像对称。
def isSymmetric(root):
"""
递归判断是否镜像对称
:param root:
:return:
"""
def is_mirror(p, q): # 判断左右子树是否镜像对称
if not p and not q: # 如果左右子树均为空
return True # 镜像对称
elif not p and q or p and not q: # 如果有且只有一棵子树为空
return False # 一定不对称
else: # 如果两棵子树都不为空
# 两棵树镜像对称的条件：根节点值相等，左左孙子和右右孙子镜像对称，左右孙子和右左孙子镜像对称
return p.val == q.val and is_mirror(p.left, q.right) and is_mirror(p.right, q.left)
return is_mirror(root, root) # 判别自身与自身是否镜像对称
测试用例：
if __name__ == '__main__':
r = create_binary_tree([1, 2, 3, 4, 5, 6, 7])
print(is_symmetric(r))
# 测试结果：False
5. 二叉树的操作
1. 二叉树的镜像
将二叉树转为其镜像二叉树。需要将根节点的左右子树交换，然后将左右子树转为其镜像树即可。
def mirror(root):
"""
将二叉树逆转
:param root:
:return:
"""
if root:
root.left, root.right = root.right, root.left # 左右子树交换
mirror(root.left) # 左右子树镜像
mirror(root.right)
测试用例：
if __name__ == '__main__':
r = create_binary_tree([1, 2, 3, 4, 5, 6, 7])
print(get_layers(r, False)) # 上文中的“之”字形遍历的层次遍历用法
mirror(r)
print(get_layers(r, False))
# 测试结果：[[1], [2, 3], [4, 5, 6, 7]]， [[1], [3, 2], [7, 6, 5, 4]]
6. 整合
我们将上述代码整合，构建一个实例化的二叉树：
class BinaryTree:
def __init__(self, node_vals):
self.tree = create_binary_tree(node_vals)
@staticmethod # 静态方法
def create_binary_tree(nodes):
def helper(node, i):
if i < len(nodes):
if nodes[i] in ['#', None]:
return None
else:
node = TreeNode(nodes[i])
node.left = helper(node.left, 2 * i + 1)
node.right = helper(node.right, 2 * i + 2)
return node
return node
root = TreeNode(0)
root = helper(root, 0)
return root
# 获取序列化结果
@property
def serialize(self):
s = lambda r: str(r.val) + ',' + s(r.left) + ',' + s(r.right) if r else "#"
return s(self.tree)
# 获取前序遍历结果，以列表形式返回
@property
def pre_order(self):
helper = lambda n: [n.val] + helper(n.left) + helper(n.right) if n else []
return helper(self.tree)
# 获取中序遍历结果，以列表形式返回
@property
def in_order(self):
helper = lambda n: helper(n.left) + [n.val] + helper(n.right) if n else []
return helper(self.tree)
# 获取后序遍历结果，以列表形式返回
@property
def post_order(self):
helper = lambda n: helper(n.left) + helper(n.right) + [n.val] if n else []
return helper(self.tree)
# 层序遍历，以嵌套列表形式返回
@property
def level_order(self):
def helper(node, level):
if not node:
return
else:
res[level - 1].append(node.val)
if len(res) == level:
res.append([])
helper(node.left, level + 1)
helper(node.right, level + 1)
res = [[]]
helper(self.tree, 1)
return res[:-1]
# 获取二叉树的最大深度
@property
def max_depth(self):
helper = lambda r: max(helper(r.left), helper(r.right))+1 if r else 0
return helper(self.tree)
# 获取二叉树的最小深度
@property
def min_depth(self):
def helper(root):
if not root:
return 0
left_min_depth = helper(root.left)
right_min_depth = helper(root.right)
if left_min_depth > 0 and right_min_depth > 0:
res = min(left_min_depth, right_min_depth) + 1
else:
res = max(left_min_depth, right_min_depth) + 1
return res
return helper(self.tree)
# 获取二叉树的所有路径
@property
def all_paths(self):
def helper(root, path, res):
cur_path = path + [root.val]
if not root.left and not root.right:
res.append(cur_path)
return
if root.left:
helper(root.left, cur_path, res)
if root.right:
helper(root.right, cur_path, res)
if not self.tree:
return []
paths = []
helper(self.tree, [], paths)
return paths
# 判断二叉树是否镜像对称
@property
def is_symmetric(self):
def helper(p, q):
if not p and not q:
return True
elif not p and q or p and not q:
return False
else:
return p.val == q.val and helper(p.left, q.right) and helper(p.right, q.left)
return helper(self.tree, self.tree)
# 将二叉树镜像翻转
def flip(self):
def helper(root):
if root:
root.left, root.right = root.right, root.left
helper(root.left)
helper(root.right)
helper(self.tree)
装饰符@property表示类属性，测试用例为：
if __name__ == '__main__':
nodes = [1, 2, 3, 4, 5, 6, 7, 8]
print('构造一棵二叉树，其结点列表为：{}.'.format(nodes))
bt = BinaryTree(nodes)
print('二叉树的序列化结果为：{}'.format(bt.serialize))
print('二叉树的前序遍历结果为：{}'.format(bt.pre_order))
print('二叉树的中序遍历结果为：{}'.format(bt.in_order))
print('二叉树的后序遍历结果为：{}'.format(bt.post_order))
print('二叉树的层序遍历结果为：{}'.format(bt.level_order))
print('二叉树的最大深度结果为：{}'.format(bt.max_depth))
print('二叉树的最小深度结果为：{}'.format(bt.min_depth))
print('二叉树的所有路径结果为：{}'.format(bt.all_paths))
print('二叉树的为镜像对称：{}'.format(bt.is_symmetric))
print('将二叉树左右翻转')
bt.flip()
print('翻转后二叉树的层序遍历结果为：{}'.format(bt.level_order))
这棵二叉树[1, 2, 3, 4, 5, 6, 7, 8]实际上是：
1
/ \
2 3
/ \ / \
4 5 6 7
/
8
测试结果为：
二叉树的序列化结果为：1,2,4,8,#,#,#,5,#,#,3,6,#,#,7,#,#
二叉树的前序遍历结果为：[1, 2, 4, 8, 5, 3, 6, 7]
二叉树的中序遍历结果为：[8, 4, 2, 5, 1, 6, 3, 7]
二叉树的后序遍历结果为：[8, 4, 5, 2, 6, 7, 3, 1]
二叉树的层序遍历结果为：[[1], [2, 3], [4, 5, 6, 7], [8]]
二叉树的最大深度结果为：4
二叉树的最小深度结果为：3
二叉树的所有路径结果为：[[1, 2, 4, 8], [1, 2, 5], [1, 3, 6], [1, 3, 7]]
二叉树的为镜像对称：False
将二叉树左右翻转
翻转后二叉树的层序遍历结果为：[[1], [3, 2], [7, 6, 5, 4], [8]]
如有疑问或建议，欢迎评论区留言~
