面试数据结构：二叉树遍历

二叉树题首先要掌握遍历。

递归模板

void dfs(TreeNode* root) {
    if (!root) return;
    visit(root);
    dfs(root->left);
    dfs(root->right);
}

三种深度优先遍历

• 前序：根、左、右。
• 中序：左、根、右。
• 后序：左、右、根。

层序遍历

层序遍历使用队列，常用于求层数、右视图、最小深度。

面试中要特别注意空节点和递归返回值的含义。

图片来源：Wikimedia Commons，二叉树结构示意图。

递归要明确返回值

二叉树题最常见的错误是递归函数含义不清楚。比如求树的最大深度：

int depth(TreeNode* root) {
    if (!root) return 0;
    return 1 + std::max(depth(root->left), depth(root->right));
}

这里 depth(root) 的含义是“以 root 为根的树的最大深度”。只要这个定义清楚，递归就会自然很多。

自顶向下与自底向上

有些题适合从根往下传状态，比如路径和；有些题适合从子树返回信息，比如平衡二叉树。判断方法是看父节点是否需要子节点的计算结果。

面试表达

写树题时，最好边写边解释递归终止条件、当前节点处理逻辑、左右子树递归关系。这比只默默写代码更能体现思路。