当前位置：首页 > news >正文

Python 算法详解：二叉树（超详细完整版）

news 2026/6/14 22:22:16

一、什么是二叉树？

1. 通俗理解

二叉树是树形数据结构，每个节点最多有两个子节点：

左孩子
右孩子

像倒挂的树：根在上，叶子在下。

2. 核心概念

根节点（root）：最顶层节点
父节点：有子节点的节点
叶子节点：没有子节点的节点
左子树、右子树
深度：树有多少层
高度：从叶子往上数的层数

3. 二叉树节点结构（必须背会）

# 二叉树节点类
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = val    # 节点值self.left = left  # 左孩子self.right = right # 右孩子

二、二叉树最核心：4 种遍历（面试必考）

二叉树最重要的就是遍历，分为 4 种：

前序遍历：根 → 左 → 右
中序遍历：左 → 根 → 右
后序遍历：左 → 右 → 根
层序遍历：一层一层遍历

三、前序遍历（根→左→右）

def preorder(root):res = []def dfs(node):if not node:returnres.append(node.val)  # 根dfs(node.left)        # 左dfs(node.right)       # 右dfs(root)return res

四、中序遍历（左→根→右）

def inorder(root):res = []def dfs(node):if not node:returndfs(node.left)        # 左res.append(node.val)  # 根dfs(node.right)       # 右dfs(root)return res

五、后序遍历（左→右→根）

def postorder(root):res = []def dfs(node):if not node:returndfs(node.left)        # 左dfs(node.right)       # 右res.append(node.val)  # 根dfs(root)return res

六、层序遍历（一层一层 BFS）

from collections import dequedef levelorder(root):res = []if not root:return resq = deque()q.append(root)while q:level = []size = len(q)for _ in range(size):node = q.popleft()level.append(node.val)if node.left:q.append(node.left)if node.right:q.append(node.right)res.append(level)return res

七、构建一棵二叉树（测试用）

# 构建如下树：
#      1
#       \
#        2
#       /
#      3
root = TreeNode(1)
root.right = TreeNode(2)
root.right.left = TreeNode(3)# 测试遍历
print("前序：", preorder(root))   # [1,2,3]
print("中序：", inorder(root))   # [1,3,2]
print("后序：", postorder(root)) # [3,2,1]
print("层序：", levelorder(root)) # [[1], [2], [3]]

八、二叉树高频经典算法（作业/面试必背）

1. 求二叉树最大深度

def max_depth(root):if not root:return 0left = max_depth(root.left)right = max_depth(root.right)return max(left, right) + 1

2. 判断是否是平衡二叉树

def is_balanced(root):def dfs(node):if not node:return 0left = dfs(node.left)right = dfs(node.right)if left == -1 or right == -1 or abs(left-right) > 1:return -1return max(left, right) + 1return dfs(root) != -1

3. 判断是否是对称二叉树

def is_symmetric(root):def check(left, right):if not left and not right:return Trueif not left or not right:return Falsereturn left.val == right.val and check(left.left, right.right) and check(left.right, right.left)return check(root.left, root.right)

4. 翻转二叉树（经典面试题）

def invert_tree(root):if not root:return None# 交换左右孩子root.left, root.right = root.right, root.leftinvert_tree(root.left)invert_tree(root.right)return root

5. 求所有根到叶子的路径

def binary_tree_paths(root):res = []def dfs(node, path):if not node:returnif not node.left and not node.right:res.append(path + str(node.val))returndfs(node.left, path + str(node.val) + "->")dfs(node.right, path + str(node.val) + "->")dfs(root, "")return res

九、完整整合代码（可直接交作业）

class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = right# 前序
def preorder(root):res = []def dfs(n):if not n: returnres.append(n.val)dfs(n.left)dfs(n.right)dfs(root)return res# 中序
def inorder(root):res = []def dfs(n):if not n: returndfs(n.left)res.append(n.val)dfs(n.right)dfs(root)return res# 后序
def postorder(root):res = []def dfs(n):if not n: returndfs(n.left)dfs(n.right)res.append(n.val)dfs(root)return res# 层序
from collections import deque
def levelorder(root):res = []if not root: return resq = deque([root])while q:level = []for _ in range(len(q)):n = q.popleft()level.append(n.val)if n.left: q.append(n.left)if n.right: q.append(n.right)res.append(level)return res# 最大深度
def max_depth(root):if not root: return 0return max(max_depth(root.left), max_depth(root.right)) + 1# 翻转二叉树
def invert(root):if not root: return Noneroot.left, root.right = root.right, root.leftinvert(root.left)invert(root.right)return root# 测试
if __name__ == "__main__":# 构建二叉树root = TreeNode(1)root.right = TreeNode(2)root.right.left = TreeNode(3)print("前序:", preorder(root))print("中序:", inorder(root))print("后序:", postorder(root))print("层序:", levelorder(root))print("最大深度:", max_depth(root))