树：倒过来的家族谱

把一棵树倒过来看：根在最上面，向下分叉长出子节点，每个节点又能再分叉。这就是数据结构里的"树"，文件目录、网页 DOM、组织架构都是树。

二叉树是树的特殊形式：每个节点最多有两个孩子（左孩子、右孩子）。别小看这个限制，二叉树是竞赛和面试里出现频率最高的树结构。

树是最"自然"的数据结构，因为世界本来就是分层组织的。
本文核心知识点
  • 节点树的组成单位。
  • 递归处理树的天然工具。
  • 遍历前中后三种顺序。
  • 深度递归求高度的经典题。
二叉树配图：蓝色渐变背景上一棵倒挂的树状结构，顶部根节点圆球向下分出两个分支圆球再分出四个分支圆球，节点间用彩色线条连接，树梢挂着几片小叶子，树下站着一个卡通小人抬头看树
根、分支、叶子——树的结构一眼就能看懂。

二叉树的术语

几个必须记住的词：根节点（最顶上的）、左孩子/右孩子（每个节点的两个分支）、叶子（没有孩子的节点）、深度（根到某节点的层数）、子树（任一节点连同它下面的部分）。

理解"子树"特别重要：每个节点向下看，都是一棵完整的树——这就是递归能派上用场的原因。

用 Python 定义节点

定义节点只要三个字段：值、左孩子、右孩子。用类或字典都可以。

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)

这段代码搭出了一棵四节点的树，画出来就是 1 下面挂着 2 和 3，2 下面挂着 4。

递归：自己调用自己

递归就是一个函数调用自己，但必须有两个要素：递归公式（怎么变小）和终止条件（什么时候停）。

求二叉树深度：一个节点的深度 = 1 + max(左子树深度, 右子树深度)，空节点深度为 0。这既是递归公式，也是终止条件。

def depth(node):
    if node is None:
        return 0
    return 1 + max(depth(node.left), depth(node.right))

三行代码，递归把整棵树的深度算出来了——这就是递归的威力。

前序、中序、后序遍历

遍历就是按顺序访问每个节点。按"根"的位置分三种：

  • 前序：根 → 左 → 右。
  • 中序：左 → 根 → 右。
  • 后序：左 → 右 → 根。
def preorder(node):
    if node is None:
        return
    print(node.val)
    preorder(node.left)
    preorder(node.right)

三种遍历的代码几乎一样，只是 print 的位置不同——理解这一点，遍历就全部拿下了。