二叉树深度优先遍历实战：计算布尔值与路径数字和

深度优先遍历简介

深度优先遍历（DFS，Depth First Traversal）是处理树或图结构时最常用的算法之一。它的核心思想是尽可能深地搜索树的分支，直到一条路径上的所有节点都被访问完毕，然后回溯到上一层继续寻找其他路径。

在二叉树中，常见的 DFS 形式包括前序、中序和后序遍历。由于树本身的定义就是递归的，用递归来实现这三种遍历不仅直观，代码也非常简洁。三种遍历的唯一区别在于访问根节点的时机不同。在实际解题中，选择合适的遍历顺序往往能事半功倍。

6. 计算布尔二叉树的值

题目描述

给定一棵非空完整二叉树，每个节点代表一个布尔运算符或叶子节点。叶子节点值为 0（false）或 1（true）。非叶子节点值为 2（OR）或 3（AND）。要求返回根节点的值。

示例

解题思路

这道题本质上是一个自底向上的求值过程。我们可以利用后序遍历的思想来处理：

1. 终止条件：当遇到叶子节点（没有左右子节点）时，直接返回该节点的值（0 或 1），因为叶子节点本身就代表了布尔结果。
2. 递归步骤：对于非叶子节点，先递归计算左右子树的值。拿到子节点的结果后，根据当前节点的类型（2 代表 OR，3 代表 AND）进行逻辑运算。

这里有个小细节，为了简化代码，我们可以在递归过程中直接修改子节点的值来存储中间结果，这样就不需要额外的变量了。当然，如果不想破坏原树结构，可以返回新的布尔值，但在这种算法题中，原地修改通常是被允许的。

C++ 代码实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool evaluateTree(TreeNode* root) {
        // 递归结束条件：叶子节点直接返回值
        if (root->left == nullptr && root->right == nullptr) {
            return root->val;
        }
        
        // 递归获取左右子树的值
        // 注意：这里利用了题目特性，将子节点的值更新为计算结果
        root->left->val = evaluateTree(root->left);
        root->right->val = evaluateTree(root->right);
        
        // 根据当前节点类型返回结果
        // 2 表示 OR，3 表示 AND
        return root->val == 2 ? (root->left->val || root->right->val) : (root->left->val && root->right->val);
    }
};

7. 求根节点到叶节点数字之和

题目描述

给定一棵二叉树，每个节点包含一个 0-9 的数字。从根到叶的路径代表一个数字（例如路径 1->2->3 代表数字 123）。求所有从根到叶路径所代表的数字之和。

示例

解题思路

这道题适合使用前序遍历（根 -> 左 -> 右），因为子节点的状态依赖于父节点传递过来的信息。

我们需要维护一个'当前路径数值'。每向下走一层，当前的数值就需要乘以 10 并加上当前节点的值。比如父节点是 1，当前节点是 2，那么路径数值就变成了 12。

关键点在于回溯：

1. 状态传递：在递归调用时，将更新后的路径数值传递给下一层。
2. 累加结果：当到达叶子节点时，说明找到了一条完整路径，将这个路径数值加入总和。
3. 汇总：左右子树的结果相加，最终返回给上一层。

同样，为了演示方便，下面的代码也采用了修改节点值的技巧来传递状态，实际工程中建议通过参数传递避免副作用。

C++ 代码实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sumNumbers(TreeNode* root) {
        // 叶子节点：直接返回自身值
        if (root->left == nullptr && root->right == nullptr) {
            return root->val;
        }
        
        int leftSum = 0, rightSum = 0;
        
        // 处理左子树
        if (root->left) {
            TreeNode* left = root->left;
            // 更新左子节点的值，相当于路径数值向前推进一位
            left->val = root->val * 10 + root->left->val;
            leftSum = sumNumbers(left);
        }
        
        // 处理右子树
        if (root->right) {
            TreeNode* right = root->right;
            // 同理更新右子节点的值
            right->val = root->val * 10 + root->right->val;
            rightSum = sumNumbers(right);
        }
        
        return leftSum + rightSum;
    }
};

流程解析

下图展示了第二道题在递归过程中的数值变化逻辑，帮助理解路径数值的累积方式：