【算法】递归算法的深度实践：从布尔运算到二叉树剪枝的DFS之旅

蒙奇D索隆

发布于 2025-11-28 19:43:00

1920

(深度优先遍历)

导读

大家好，很高兴又和大家见面啦！！！在上一篇中，我们探讨了如何利用深度优先搜索（DFS）的中序遍历特性，在二叉搜索树中高效地查找第K小的元素。我们看到了 DFS 如何通过递归自然地深入树的分支，系统地访问每个节点。 DFS 的核心思想在于“一路到底，再逐步回溯”。这种策略在解决树形结构的问题时尤为强大。今天，我们将继续深入这一主题，通过两道经典的二叉树问题，进一步巩固 DFS 的理解与应用，特别关注其 后序遍历形式 的强大威力。现在，让我们进入正文，一起探索 DFS 的实践魅力。

一、2331. 计算布尔二叉树的值

1.1 题目介绍

题目标签：树、深度优先搜索、二叉树、第82场双周赛 题目难度：简单 题目描述：给你一棵完整二叉树的根，这棵树有以下特征：

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

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

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

返回根节点 root 的布尔运算值。 完整二叉树 是每个节点有 0 个或者 2 个孩子的二叉树。 叶子节点 是没有孩子的节点。 示例 1：输入：root = [2, 1, 3, null, null, 0, 1] 输出：true

flowchart TB
a[2<br>or]
b[1]
c[3<br>and]
d[0]
e[1]
a--->b
a--->c
c--->d
c--->e

解释：ret = 1 or (0 and 1) = true。 AND 与运算节点的值为 False AND True = False 。 OR 运算节点的值为 True OR False = True 。根节点的值为 True ，所以我们返回 true 。

示例 2：输入：root = [0] 输出：false

flowchart TB
a[0]

解释：ret = 0

根节点是叶子节点，且值为 false，所以我们返回 false 。提示：树中节点数目在 [1, 1000] 之间。 0 \leq Node.val \leq 3 每个节点的孩子数为 0 或 2 。叶子节点的值为 0 或 1 。非叶子节点的值为 2 或 3 。

1.2 解题思路

该题比较简单，其结果主要由三部分构成：

左子树：值为 1 或者 0
根节点：运算符为 or 或者 and
右子树：值为 1 或者 0

因此整棵树的值，我们只需要依次计算出左子树和右子树后，在将二者通过根节点的运算符完成运算即可；而这个二叉树的左右子树均可以通过将其分解为三部分，即，树中的每棵子树的值均是由：

左子树的值
根节点的运算符
右子树的值

这三部分构成。这种 分而治之 的分解思想正是递归的算法思想，而递归在 数据结构 中的应用正是 深度优先搜索 算法。在前面我们介绍过，二叉树 的 中序遍历 正是 DFS 的表现形式，但是这并不意味着 中序遍历 就是二叉树中的 DFS 。对于二叉树中的 深度优先搜索 ，我们应该理解为：

深度优先 策略在 二叉树 中的应用

而该应用在 二叉树 中有三种表现形式：

先序
中序
后序

因此不管是哪种表现形式，我们均可以将其称为 二叉树 中的 深度优先 策略。当该策略 + 搜索目的后，就得到了 二叉树 中的 深度优先搜索；在本题中，我们要想获得一棵树的布尔值，我们就需要先获取左右子树的值，在通过根节点将二者进行运算，因此该二叉树的遍历顺序为：

左子树 \rightarrow 右子树 \rightarrow 根结点

该遍历顺序对应的正是 二叉树 中的 后序遍历，也就是说我们要解决本题的具体方式为：

使用 深度优先策略 以后序的形式对该 二叉树 进行遍历获取 二叉树 的布尔值

1.3 代码编写

明确了具体的解题思路后，接下来我们就需要开始编写相应的代码了。

1.3.1 定义函数

该函数的目的是：

通过 深度优先 策略对该 二叉树 以后序的形式完成遍历获取树的布尔值；

因此我们可以采用多种命名方式：

DFT —— 深度优先搜索
DFS —— 深度优先遍历
Post_Order —— 后序遍历

这里我们还是使用 DFS 作为函数名，函数的返回类型为 bool ，函数的参数为树的根节点 root：

bool dfs(struct TreeNode* root) {
	
}

1.3.2 递归基

在树中，都是以判断树是否为空作为递归基，在这题中，我们则可以通过各结点的值作为函数的递归基：

	if (root->val == 1) {
		return true;
	}
	if (root->val == 0) {
		return false;
	}
	if (root->val == 2) {
		return left || right;
	}
	return left && right;

当结点的值为 0 表示该结点为叶子结点，且对应的值为 false；当结点的值为 1 表示该结点为叶子结点，且对应的值为 true；当结点的值为 2 表示该节点为非叶子结点，且对应的值为 left || right；当结点的值为 3 表示该节点为非叶子结点，且对应的值为 left && right；

1.3.3 递进关系

在二叉树中，其递进关系就是该棵树的左右子树：

	bool left = dfs(root->left);
	bool right = dfs(root->right);

1.3.4 组合优化

当我们将上述内容进行整合，就得到了最终的代码：

bool dfs(struct TreeNode* root) {
	if (root->val == 1) {
		return true;
	}
	if (root->val == 0) {
		return false;
	}
	bool left = dfs(root->left);
	bool right = dfs(root->right);
	if (root->val == 2) {
		return left || right;
	}
	return left && right;
}

bool evaluateTree(struct TreeNode* root) {
	return dfs(root);
}

1.4 代码测试

下面我们就在 leetcode 中对该代码进行测试：

二、814. 二叉树剪枝

2.1 题目介绍

题目标签：树、深度优先搜索、二叉树 题目难度：中等 题目描述：给你二叉树的根结点 root ，此外树的每个结点的值要么是 0 ，要么是 1。返回移除了所有不包含 1 的子树的原二叉树。节点 node 的子树为 node 本身加上所有 node 的后代。 示例 1：输入：root = [1, null, 0, 0, 1] 输出：[1, null, 0, null, 1]

flowchart LR
	subgraph t[原树]
		direction TB
		a((1))
		a--->a1((NULL))
		b((0))
		a--->b
		c((0))
		d((1))
		b--->c
		b--->d
	end

	subgraph T[剪枝后]
		direction TB
		A((1))
		A--->A1((NULL))
		B((0))
		A--->B
		C((NULL))
		D((1))
		B--->C
		B--->D
	end

t--->T
classDef red fill: #ff9999, color: #000, stroke: #ff0000, stroke-width: 2px
class c red
class C red

解释：只有红色节点满足条件“所有不包含 1 的子树”。右图为返回的答案。 示例 2：输入：root = [1, 0, 1, 0, 0, 0, 1] 输出：[1, null, 1, null, 1]

flowchart LR
	subgraph t[原树]
		direction TB
		a((1))
		b((0))
		c((1))
		a--->b
		a--->c
		e((0))
		f((0))
		b--->e
		b--->f
		g((0))
		h((1))
		c--->g
		c--->h
	end

	subgraph T[剪枝后]
		direction TB
		A((1))
		B((NULL))
		C((1))
		A--->B
		A--->C
		
		G((NULL))
		H((1))
		C--->G
		C--->H
	end

t--->T

classDef red fill: #ff9999, color: #000, stroke: #ff0000, stroke-width: 2px
class b red
class e red
class f red
class g red
class B red
class G red

示例 3：输入：root = [1, 1, 0, 1, 1, 0, 1, 0] 输出：[1, 1, 0, 1, 1, null, 1]

flowchart LR
	subgraph t[原树]
		direction TB
		a((1))
		b((1))
		c((0))
		a--->b
		a--->c
		d((1))
		e((1))
		b--->d
		b--->e
		f((0))
		g((1))
		c--->f
		c--->g
		h((0))
		d--->h
	end

	subgraph T[剪枝后]
		direction TB
		A((1))
		B((1))
		C((0))
		A--->B
		A--->C
		D((1))
		E((1))
		B--->D
		B--->E
		F((NULL))
		G((1))
		C--->F
		C--->G
		
	end

t--->T

classDef red fill: #ff9999, color: #000, stroke: #ff0000, stroke-width: 2px

class f red
class h red
class F red

提示：树中节点的数目在范围 [1, 200] 内 Node.val 为 0 或 1

2.2 解题思路

该题的解题思路很简单，我们判断一棵子树是否需要被剪枝，我们只需要判断其左右子树以及根结点中是否存在 1 ：

存在，则不进行剪枝
不存在，则进行剪枝

因此，我们在决定是否要进行剪枝操作前，我们需要先检查该子树的左右子树，具体的操作算法，我们可以通过 深度优先 策略，并以后序的形式对该棵树进行遍历；

2.3 代码编写

2.3.1 函数定义

该函数的目的为：

通过 深度优先 策略，并以后序的形式对该棵树进行遍历

而遍历的目的是为了判断是否执行剪枝操作：

树中存在 1 则不执行任何操作
树中不存在 1 则执行剪枝操作

因此函数的返回类型为 bool：

bool DFS(struct TreeNode* root) {

}

2.3.2 递归基

在该函数中，我们需要根据左右子树以及根节点来判断是否需要进行剪枝：

	if (root == NULL) {
		return true;
	}

	if (left && right && root->val == 0) {
		return true;
	}
	return false;

当该树为空树时，则表示该结点需要进行剪枝，即返回 true；当树为非空树，且其左右子树均为需要剪枝，且该结点的值为 0 ，则表示该结点需要进行剪枝，即返回 true；当树为非空树，且该结点的值为 1 ，则表示该结点不需要进行剪枝，即返回 false；

2.3.3 递进关系

在二叉树中，其递进关系为其左右子树：

	bool left = DFS(root->left);
	bool right = DFS(root->right);

2.3.4 组合优化

当我们将上面的内容进行整合，并加入剪枝操作后，即可得到完整的代码：

bool DFS(struct TreeNode** root) {
	if (*root == NULL) {
		return true;
	}
	bool left = DFS(&((*root)->left));
	bool right = DFS(&((*root)->right));
	if (left && right && (*root)->val == 0) {
		free(*root);
		*root = NULL;
		return true;
	}
	return false;
}
struct TreeNode* pruneTree(struct TreeNode* root) {
	bool ret = DFS(&root);
	return root;
}

需要注意的是，由于剪枝操作是直接更改相应的二叉树，因此我们需要以指针的形式进行传参；