二叉树

0 Basic 二叉树是什么? 每个节点最多有两个子节点（左子节点、右子节点）的树结构。 1 ← 根节点 (root) / \ 2 3 ← 深度 1 / \ \ 4 5 6 ← 深度 2（叶子节点） Python节点定义 1class TreeNode: 2 def __init__(self, val=0, left=None, right=None): 3 self.val = val 4 self.left = left 5 self.right = right 四种遍历方式 1# 前序遍历（Pre-order）：根 → 左 → 右 2def preorder(root): 3 if not root: return 4 print(root.val) # 先处理根 5 preorder(root.left) 6 preorder(root.right) 7 8# 中序遍历（In-order）：左 → 根 → 右 9def inorder(root): 10 if not root: return 11 inorder(root.left) 12 print(root.val) # 中间处理根 13 inorder(root.right) 14 15# 后序遍历（Post-order）：左 → 右 → 根 16def postorder(root): 17 if not root: return 18 postorder(root.left) 19 postorder(root.right) 20 print(root.val) # 最后处理根 21 22# 层序遍历（Level-order）：BFS，逐层从左到右 23from collections import deque 24def levelorder(root): 25 if not root: return 26 queue = deque([root]) 27 while queue: 28 node = queue.popleft() 29 print(node.val) 30 if node.left: queue.append(node.left) 31 if node.right: queue.append(node.right) 记忆口诀： 前/中/后指的是根节点在遍历中的位置（前面、中间、后面），左右顺序永远是先左后右。 ...