一文详解“二叉树中的深搜“在算法中的应用
找往期文章包括但不限于本期文章中不懂的知识点：
个人主页：我要学编程(ಥ_ಥ)-CSDN博客
所属专栏： 递归、搜索与回溯算法专题
目录
深搜的介绍
2331.计算布尔二叉树的值
129.求根节点到叶节点数字之和
814.二叉树剪枝
98.验证二叉搜索树
230.二叉搜索树中第K小的元素
257.二叉树的所有路径
深搜的介绍
深搜是深度优先遍历（深度优先搜索）的一种简称。那什么是深度优先遍历呢？对于单分支的情况来说，就是直接暴力遍历，例如，遍历顺序表、链表的情况。对于多分支的情况来说，深度优先遍历就是一条道走到黑（或者说不撞南墙不回头，但是撞了就立马回头），沿着某条路径一直走直至不能走下去了，再返回去沿着其他路径走，最典型的代表：二叉树中的前序遍历、中序遍历、后序遍历都是深度优先遍历的形式。因为不管是前序、中序、后序，它们都是沿着某条路线一直走到不能走了才返回。
接下来我们通过一些题目来认识"深搜"。
2331.计算布尔二叉树的值
题目：
给你一棵 完整二叉树 的根，这棵树有以下特征：
- 叶子节点 要么值为
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 解释：上图展示了计算过程。 AND 与运算节点的值为 False AND True = False 。 OR 运算节点的值为 True OR False = True 。 根节点的值为 True ，所以我们返回 true 。示例 2：
输入：root = [0] 输出：false 解释：根节点是叶子节点，且值为 false，所以我们返回 false 。提示：
- 树中节点数目在
[1, 1000]之间。0 <= Node.val <= 3- 每个节点的孩子数为
0或2。- 叶子节点的值为
0或1。- 非叶子节点的值为
2或3。
思路：要知道整棵树的布尔值，得先知道其左子树与右子树的布尔值，然后再通过根结点的运算符来计算最终的结果，而想知道左子树的布尔值，还得知道其左子树与右子树的布尔值，然后再通过左子树的运算符来计算。这里我们已经找到了重复子问题了（针对二叉树的问题，是很容易就找到重复子问题）。
代码实现：
class Solution {
// 计算出root指针指向的树的布尔值
public boolean evaluateTree(TreeNode root) {
if (root.left == null && root.right == null) { // 叶子结点
return root.val == 1 ? true : false;
}
// 先得计算出左子树
boolean left = evaluateTree(root.left);
// 再去计算右子树
boolean right = evaluateTree(root.right);
// 再根据根结点的值来计算出最终结果
if (root.val == 2) { // or
return left || right;
} else { // and
return left && right;
}
}
}这里其实就是一个后序遍历。
129.求根节点到叶节点数字之和
题目：
给你一个二叉树的根节点
root，树中每个节点都存放有一个0到9之间的数字。每条从根节点到叶节点的路径都代表一个数字：
- 例如，从根节点到叶节点的路径
1 -> 2 -> 3表示数字123。计算从根节点到叶节点生成的 所有数字之和 。
叶节点 是指没有子节点的节点。
示例 1：
输入：root = [1,2,3] 输出：25 解释： 从根到叶子节点路径 1->2 代表数字 12 从根到叶子节点路径 1->3 代表数字 13 因此，数字总和 = 12 + 13 = 25示例 2：
输入：root = [4,9,0,5,1] 输出：1026 解释： 从根到叶子节点路径 4->9->5 代表数字 495 从根到叶子节点路径 4->9->1 代表数字 491 从根到叶子节点路径 4->0 代表数字 40 因此，数字总和 = 495 + 491 + 40 = 1026提示：
- 树中节点的数目在范围
[1, 1000]内0 <= Node.val <= 9- 树的深度不超过
10
思路：
代码实现：
class Solution {
public int sumNumbers(TreeNode root) {
return dfs(root, 0);
}
private int dfs(TreeNode root, int prevSum) {
// 把当前路径的值计算出来
prevSum = prevSum * 10 + root.val;
// 判断当前结点是否为叶子结点
if (root.left == null && root.right == null) {
return prevSum;
}
// 可能会存在左子树为空，右子树不为空；左子树不为空，右子树为空的情况
// 这里没有去判断当前结点是否为null的情况，可能会出现空指针异常
int sum = 0;
if (root.left != null) {
sum += dfs(root.left, prevSum);
}
if (root.right != null) {
sum += dfs(root.right, prevSum);
}
return sum;
}
}814.二叉树剪枝
题目：
给你二叉树的根结点
root，此外树的每个结点的值要么是0，要么是1。返回移除了所有不包含
1的子树的原二叉树。节点
node的子树为node本身加上所有node的后代。示例 1：
输入：root = [1,null,0,0,1] 输出：[1,null,0,null,1] 解释： 只有红色节点满足条件“所有不包含 1 的子树”。 右图为返回的答案。示例 2：
输入：root = [1,0,1,0,0,0,1] 输出：[1,null,1,null,1]示例 3：
输入：root = [1,1,0,1,1,0,1,0] 输出：[1,1,0,1,1,null,1]提示：
- 树中节点的数目在范围
[1, 200]内Node.val为0或1
思路：题目这里是让我们将二叉树中只包含数值0的结点的所在的子树给剪枝，也就是删除（置为null即可）。这里要删除就得判断其左子树是否符合只包含0，其右子树是否符合只包含0，并且当前结点的值是0，如果是的话，就得将这棵树删除，也就是置为null。
代码实现：
class Solution {
// 函数的意义：给你一个根结点，把根结点所指向的树中只有0的子树给去除
public TreeNode pruneTree(TreeNode root) {
// 递归的出口
if (root == null) {
return null;
}
// 处理左子树
TreeNode left = pruneTree(root.left);
// 如果左子树为null，就得"剪枝"
if (left == null) {
root.left = null;
}
// 处理右子树
TreeNode right = pruneTree(root.right);
// 如果右子树为null，就得"剪枝"
if (right == null) {
root.right = null;
}
// 处理当前结点
if (left == null && right == null && root.val == 0) {
return null;
}
return root;
}
}98.验证二叉搜索树
题目：
给你一个二叉树的根节点
root，判断其是否是一个有效的二叉搜索树。有效 二叉搜索树定义如下：
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
输入：root = [2,1,3] 输出：true示例 2：
输入：root = [5,1,4,null,null,3,6] 输出：false 解释：根节点的值是 5 ，但是右子节点的值是 4 。提示：
- 树中节点数目范围在
[1, 104]内-231 <= Node.val <= 231 - 1
思路：本题就是让我们想办法证明这棵二叉树是二叉搜索树。很简单，二叉搜索树的性质：中序遍历二叉树，最终的序列是有序的。因此可以直接用一个数组暴力存储所有的值，然后去判断该数组是否有序即可。暴力方法虽然行得通，但还可以优化，我们要证明有序的话，可以用一个变量来记录前一个位置的值，当前一个位置的值小于当前位置的时候，说明是满足二叉搜索树的性质，那就继续判断下去，而如果不满足的话，那就直接返回false即可。最终遍历完成并未返回false，说明这棵树确实是二叉搜索树。
代码实现：
暴力解法：
class Solution {
int[] nums;
int i = 0;
public boolean isValidBST(TreeNode root) {
nums = new int[100001];
// 中序遍历判断是否为有序序列即可
dfs(root);
for (int j = 0; j < i; j++) {
if (j+1 < i && nums[j] >= nums[j+1]) {
return false;
}
}
return true;
}
void dfs(TreeNode root) {
if (root == null) {
return;
}
dfs(root.left);
nums[i++] = root.val;
dfs(root.right);
}
}优化解法：
class Solution {
// 使用一个变量来记录中序遍历的前一个数值
long prev = Long.MIN_VALUE;
// 函数的意义：给你一个root，判断其指向的树是否为二叉搜索树
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
// 判断左子树是否为二叉搜索树
boolean left = isValidBST(root.left);
if (!left) { // 如果为false，那么后面的就不需要判断了
return false;
}
// 判断当前结点是否符合二叉搜索树的定义
if (root.val > prev) {
prev = root.val;
} else {
return false;
}
// 判断右子树是否为二叉搜索树
boolean right = isValidBST(root.right);
if (!right) { // 如果为false，那么后面的就不需要判断了
return false;
}
return true;
}
}230.二叉搜索树中第K小的元素
题目：
给定一个二叉搜索树的根节点
root，和一个整数k，请你设计一个算法查找其中第k小的元素（从 1 开始计数）。示例 1：
输入：root = [3,1,4,null,2], k = 1 输出：1示例 2：
输入：root = [5,3,6,2,4,null,null,1], k = 3 输出：3提示：
- 树中的节点数为
n。1 <= k <= n <= 10^40 <= Node.val <= 10^4
思路：这一题本质上与上一题是差不多的，还是利用二叉搜索树的性质来解题。暴力解法就是中序遍历遍历整个二叉搜索树，将节点存储起来，然后返回第k-1个元素即可。优化的话，就是使用两个全局变量：一个去记录k的值，一个去记录最终返回的结果。
代码实现：
暴力解法：
class Solution {
// 用一个数组将二叉搜索树的中序遍历存储起来
int[] nums;
int i;
public int kthSmallest(TreeNode root, int k) {
nums = new int[10001];
i = 0;
dfs(root);
return nums[k-1];
}
private void dfs(TreeNode root) {
if (root == null) {
return;
}
dfs(root.left);
nums[i++] = root.val;
dfs(root.right);
}
}优化解法：
class Solution {
// 函数的意义：找到root树的第k小的结点
int count, ret;
public int kthSmallest(TreeNode root, int k) {
count = k;
dfs(root);
return ret;
}
private void dfs(TreeNode root) {
if (root == null || count == 0) {
return;
}
dfs(root.left);
if (--count == 0) {
ret = root.val;
return;
}
dfs(root.right);
}
}257.二叉树的所有路径
题目：
给你一个二叉树的根节点
root，按 任意顺序 ，返回所有从根节点到叶子节点的路径。叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [1,2,3,null,5] 输出：["1->2->5","1->3"]示例 2：
输入：root = [1] 输出：["1"]提示：
- 树中节点的数目在范围
[1, 100]内-100 <= Node.val <= 100
思路：题目是让我们将根结点到每个叶子结点的路径统计出来。其实也是比较简单的，只需要用一个字符串变量来记录当前的元素信息，如果是叶子结点的话，就存储到 List 中，反之则继续向下探索。
代码实现：
class Solution {
List<String> l;
public List<String> binaryTreePaths(TreeNode root) {
l = new LinkedList<>();
StringBuilder path = new StringBuilder();
dfs(root, path);
return l;
}
private void dfs(TreeNode root, StringBuilder _path) {
// 新创建一个path变量，虽然值一样，但是地址并不一样
// 这样每次在递归修改的时候，并不会相互影响，而是自己新创建的对象
StringBuilder path = new StringBuilder(_path);
if (root.left == null && root.right == null) {
path.append(root.val);
l.add(path.toString());
return;
} else {
path.append(root.val);
path.append("->");
}
if (root.left != null) {
dfs(root.left, path);
}
if (root.right != null) {
dfs(root.right, path);
}
}
}注意：这里在统计完叶子结点之后，回溯的过程中，之前的 StringBuilder 变量已经发生了变化，并不是我们第一次来时的摸样了，这就需要我们去还原刚开始的样子，可以在每递归一次的时候，就去创建一个新的变量来记录当前的变化情况。