二叉树 DFS 递归解题套路

深度优先遍历（DFS）是树或图结构中常用的遍历算法。它会尽可能深地搜索分支，直到路径末端再回溯。在二叉树中，DFS 通常表现为前序、中序和后序遍历。由于树的定义本身是递归的，使用递归实现这三种遍历不仅易于理解，代码也十分简洁。三者的核心区别仅在于访问根节点的时机不同。

1. 计算布尔二叉树的值

题目链接：2331. 计算布尔二叉树的值 题目描述：

算法原理：递归（后序遍历） 本题的核心是自底向上递归计算完整二叉树的布尔运算值，本质是对二叉树后序遍历的应用。

1. 问题拆解

• 叶子节点：值为 0（False）或 1（True），直接返回对应的布尔值。
• 非叶子节点：值为 2（OR）或 3（AND），需先计算左右子节点的值，再用当前节点的运算符对子结果进行逻辑运算。

2. 递归逻辑

• 终止条件：若当前节点为叶子节点（无左右子节点），直接将节点值转为布尔值返回（0→False，1→True）。
• 递归步骤：
  • 递归计算左子树的布尔结果。
  • 递归计算右子树的布尔结果。
  • 根据当前节点运算符返回结果：若为 2（OR）返回 左结果 || 右结果；若为 3（AND）返回 左结果 && 右结果。
• 最终结果：根节点的递归返回值即为整棵树的布尔运算结果。

示例代码

class Solution {
    public boolean evaluateTree(TreeNode root) {
        if (root.left == null) return root.val == 0 ? false : true;
        boolean left = evaluateTree(root.left);
        boolean right = evaluateTree(root.right);
        return root.val ==  ? (left || right) : (left && right);
    }
}