二叉树递归遍历与剪枝算法详解

二叉树递归遍历与剪枝算法详解

1. 前言

深度优先遍历（DFS，全称为 Depth First Traversal）是树或图结构中常用的遍历算法。该算法会尽可能深地搜索树或图的分支，直到一条路径上的所有节点都被遍历完毕，然后再回溯到上一层，继续寻找其他路径。

在二叉树中，常见的深度优先遍历包括：前序遍历、中序遍历以及后序遍历。由于树的定义本身是递归定义，采用递归的方法实现这三种遍历不仅容易理解，而且代码简洁。前、中、后序三种遍历的唯一区别在于访问根节点的时机不同。选择合适的遍历顺序对算法理解非常有帮助。

2. 计算布尔二叉树的值

题目链接：计算布尔二叉树的值

题目介绍

给你一棵完整二叉树的根，这棵树有以下特征：

• 叶子节点要么值为 0 要么值为 1，其中 0 表示 False，1 表示 True。
• 非叶子节点要么值为 2 要么值为 3，其中 2 表示逻辑或 OR，3 表示逻辑与 AND。

计算一个节点的值方式如下：

• 如果节点是个叶子节点，那么节点的值为它本身，即 True 或者 False。
• 否则，计算两个孩子的节点值，然后将该节点的运算符对两个孩子值进行运算。

返回根节点 root 的布尔运算值。

算法思路

1. 对于规模为 n 的问题，需要求得当前节点值。
2. 节点值不为 0 或 1 时，规模为 n 的问题可以被拆分为规模为 n-1 的子问题：
   • 获取所有子节点的值；
   • 通过子节点的值运算出当前节点值。
3. 当问题的规模变为 n=1 时（即叶子节点的值为 0 或 1），可以直接获取当前节点值。

递归函数流程

1. 当前问题规模为 n=1 时，即叶子节点，直接返回当前节点值。
2. 递归求得左右子节点的值。
3. 判断当前节点的逻辑运算符，计算左右子节点值运算得出的结果。

代码示例

class Solution {
public:
    bool evaluateTree(TreeNode* root) {
        if (root->left == nullptr || root->right == nullptr) {
            return root->val;
        } else {
            if (root->val == 2) return evaluateTree(root->left) || evaluateTree(root->right);
            else return evaluateTree(root->left) && evaluateTree(root->right);
        }
    }
};