深度优先遍历介绍
在树或图结构中，深度优先遍历（DFS）是一种基础且常用的算法。它尽可能深地搜索分支，直到路径结束再回溯。二叉树中常见的前序、中序和后序遍历，核心区别仅在于访问根节点的时机不同。由于树的定义本身具有递归性质，用递归实现这些遍历既直观又简洁。
在做题时，选择合适的遍历顺序对理解算法逻辑非常有帮助。下面我们通过两个经典题目来实战 DFS 的应用。
6. 计算布尔二叉树的值
题目描述
给定一棵非空二叉树，每个节点代表一个布尔值或逻辑运算。叶子节点值为 0（False）或 1（True）。非叶子节点值为 2（OR）或 3（AND）。需要返回根节点的计算结果。
解题思路
这是一个典型的后序遍历场景。我们需要先处理子节点，再根据当前节点的类型组合结果。
- 终止条件：如果当前节点是叶子节点，直接返回其值。
- 递归步骤：分别计算左右子树的值。
- 合并结果：若节点值为 2，返回左右子树值的 OR 运算；若为 3，返回 AND 运算。
C++ 代码实现
class Solution {
public:
bool evaluateTree(TreeNode* root) {
// 叶子节点直接返回值
if (!root->left && !root->right) {
return root->val;
}
// 递归获取子节点结果
bool leftVal = evaluateTree(root->left);
bool rightVal = evaluateTree(root->right);
// 根据节点类型进行逻辑运算
return root->val == 2 ? (leftVal || rightVal) : (leftVal && rightVal);
}
};
这里要注意，递归的终止条件非常关键。当遇到叶子节点时，我们不需要继续向下，直接返回即可。对于内部节点，我们利用逻辑运算符的特性将子问题的解合并。
7. 求根节点到叶节点数字之和
题目描述
给定一个二叉树，每个节点的值都在 0-9 之间。从根节点到叶节点的路径可以表示为一个数字。例如路径 1->2->3 表示数字 123。要求计算所有根到叶路径表示的数字之和。
解题思路
这道题适合使用前序遍历。因为子节点的状态依赖于父节点传递过来的信息。
- 状态传递：在递归过程中，我们将父节点累积的数字乘以 10 加上当前节点的值，形成新的路径数值传递给下一层。
- 累加结果：当到达叶子节点时，说明一条完整路径结束，将该路径代表的数值加入总和。
- 回溯：递归返回时，左右子树的结果相加即为当前节点贡献的和。
C++ 代码实现
class Solution {
public:
int sumNumbers(TreeNode* root) {
// 辅助函数，携带当前路径数值
return dfs(root, 0);
}
private:
int dfs(TreeNode* node, int currentSum) {
if (!node) return 0;
// 更新当前路径数值
currentSum = currentSum * 10 + node->val;
// 如果是叶子节点，返回当前路径数值
if (!node->left && !node->right) {
return currentSum;
}
// 否则继续递归左右子树并累加
return dfs(node->left, currentSum) + dfs(node->right, currentSum);
}
};
相比直接在原树上修改节点值，使用辅助函数传递 currentSum 更加清晰且不会破坏原始数据结构，这是工程实践中更推荐的做法。
总结
通过这两个题目，我们可以看到 DFS 在不同场景下的灵活应用：
- 计算布尔二叉树的值：侧重于自底向上的归约，利用后序遍历特性，先解决子问题再合并。
- 求根节点到叶节点数字之和：侧重于自上而下的传递，利用前序遍历特性，在递归过程中维护状态。
掌握这两种模式，能帮助你更高效地解决大多数二叉树相关的递归问题。