【算法系列篇】递归、搜索和回溯（三）

刺骨的言语ヽ痛彻心扉 2024-02-05 15:05 36阅读 0赞

![在这里插入图片描述][ad21b455de0b4510ace6d27c2f7079b0.gif_pic_center]

#### 文章目录 ####

*  前言
 *  什么是二叉树剪枝
 *  1. 二叉树剪枝
 *   *  1.1 题目要求
     *  1.2 做题思路
     *  1.3 代码实现
 *  2. 验证二叉搜索树
 *   *  2.1 题目要求
     *  2.2 做题思路
     *  2.3 代码实现
 *  3. 二叉搜索树中第k小的元素
 *   *  3.1 题目要求
     *  3.2 做题思路
     *  3.3 代码实现
 *  4. 二叉树的所有路径
 *   *  4.1 题目要求
     *  4.2 做题思路
     *  4.3 代码实现

## 前言 ##

前面我已经给大家分享了两篇关于递归、搜索和回溯相关的问题，但是前面两篇只涉及到了递归，搜索和回溯基本还没涉及到，大家先别着急，后面的文章会为大家分享关于搜索和回溯相关的知识和题目。今天这篇文章主要涉及到的就是关于在递归过程中的剪枝问题。

## 什么是二叉树剪枝 ##

二叉树剪枝是指通过剪去二叉树中某些子树来提高其质量的过程。具体来说，二叉树剪枝可以包括以下几种情况：

1.  剪去二叉树中所有空子树：当二叉树中存在空子树时，这些空子树不会对整个二叉树的性能产生任何影响，因此可以将它们全部剪去。
2.  剪去二叉树中重复的子树：当二叉树中存在重复的子树时，这些重复的子树会对整个二叉树的性能产生负面影响，因此可以将它们全部剪去。
3.  剪去二叉树中不必要的子树：当二叉树中存在一些不必要的子树时，这些子树不会对整个二叉树的性能产生任何影响，因此可以将它们全部剪去。

通过二叉树剪枝，可以提高二叉树的性能和效率，使得它更加适合于解决实际问题。

其实二叉树剪枝不困难，只需要我们在递归的过程中做出适当的判断就可以到达剪枝的目的。

## 1. 二叉树剪枝 ##

[https://leetcode.cn/problems/binary-tree-pruning/][https_leetcode.cn_problems_binary-tree-pruning]

### 1.1 题目要求 ###

给你二叉树的根结点 root ，此外树的每个结点的值要么是 0 ，要么是 1 。

返回移除了所有不包含 1 的子树的原二叉树。

节点 node 的子树为 node 本身加上所有 node 的后代。

示例 1：  
![在这里插入图片描述][d51ea9133d534f498cdbeee24e751a4f.png]

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

示例 2：  
![在这里插入图片描述][92458fc3e25342d49c279ce1dabc35cb.png]

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

示例 3：  
![在这里插入图片描述][61cd32a87286425bbd3a55acb176fb33.png]

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

提示：

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

### 1.2 做题思路 ###

想要做好递归，我们需要以宏观的视角来解决微观问题。首先先来判断给我们的节点是否是null，如果是则直接返回null，不是，则将根节点的左子树和右子树分别交给函数，通过这个函数，我们不需要知道这个函数的具体细节，我们只需要相信他一定能够帮助我们完成剪枝操作。当根节点的左右子树都完成剪枝操作之后，就进行判断，如果根节点的左右子树都为null，并且根节点的值为0，那么就可以将根节点置为null，然后返回root。

![在这里插入图片描述][caa66dccc65d424b85d1e360cb83e547.png]  
![在这里插入图片描述][2e3f03bc1c9e4a7c9dfb493a4d8e0c4d.png]

### 1.3 代码实现 ###

![在这里插入图片描述][3dba7be3acfa441e9e7025ba903ffb07.png]

## 2. 验证二叉搜索树 ##

[https://leetcode.cn/problems/validate-binary-search-tree/][https_leetcode.cn_problems_validate-binary-search-tree]

### 2.1 题目要求 ###

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

节点的左子树只包含 小于 当前节点的数。  
节点的右子树只包含 大于 当前节点的数。  
所有左子树和右子树自身必须也是二叉搜索树。

示例 1：  
![在这里插入图片描述][ca068a7f54f542ae8216799b7e6d6e29.png]

输入：root = [2,1,3]
    输出：true

示例 2：  
![在这里插入图片描述][8b584568256f4b4992b92de6035bb7bb.png]

输入：root = [5,1,4,null,null,3,6]
    输出：false
    解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

树中节点数目范围在[1, 104] 内
    -231 <= Node.val <= 231 - 1

### 2.2 做题思路 ###

我们都知道二叉搜索树是二叉树中的任何一个如果左右孩子存在，那么该节点左孩子节点的值要小于该节点的值，并且该节点的值要小于该节点右孩子节点的值，也就是说：二叉搜索树使用中序遍历的话得到的是一个升序的数字。那么在这道题目中，我们该如何判断某个节点的左孩子节点的值小于该节点的值，右孩子节点的值大于该节点的值呢？

我们可以使用前序遍历的方法，先找到二叉搜索树中最小的节点，然后用 prev 记录这个值，返回的时候，就先判断该节点的左子树是否符合二叉搜索树，如果不符合就可以直接返回 false，如果符合的话就需要将 prev 的值与 root 的 val 进行比较，如果 prev < root.val，那么将 prev 的值替换为当前节点的值，并且继续去判断该节点右子树是否为二叉搜索树。

![在这里插入图片描述][92d20c3c3f8b482aacf58214dee2a376.png]  
![在这里插入图片描述][8ee5cdab39d54252aa70c7a79f91493b.png]

### 2.3 代码实现 ###

![在这里插入图片描述][d502e7e1c440471b90456ca14fa4235b.png]

## 3. 二叉搜索树中第k小的元素 ##

[https://leetcode.cn/problems/kth-smallest-element-in-a-bst/][https_leetcode.cn_problems_kth-smallest-element-in-a-bst]

### 3.1 题目要求 ###

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

示例 1：  
![在这里插入图片描述][4f09751f310f46b7b86178f1a6d2f655.png]

输入：root = [3,1,4,null,2], k = 1
    输出：1

示例 2：  
![在这里插入图片描述][4aa57171c4ab4a9fa9f1443529222071.png]

输入：root = [5,3,6,2,4,null,null,1], k = 3
    输出：3

提示：

树中的节点数为 n 。
    1 <= k <= n <= 104
    0 <= Node.val <= 104

### 3.2 做题思路 ###

这道题目可以使用优先级队列来解决，但是为了加强递归的使用，我们不使用优先级队列，而是使用递归来解决这个问题，根据二叉树的特性，要想找到二叉搜索树中第k小的元素，我们可以使用中序遍历二叉搜索树的方法，并且使用全局变量count 来记录当前遍历的节点是第几小的元素，以及使用一个全局变量 ret 来记录第 k 小的元素，中序遍历，没遍历一个节点，count就–，如果 count 为 0，就说明找到了这个元素。

在递归中，有些情况使用全局变量可以使得我们的代码变得很简单。

### 3.3 代码实现 ###

![在这里插入图片描述][3a8c6a6d03b541749d4341f700768f73.png]

## 4. 二叉树的所有路径 ##

[https://leetcode.cn/problems/binary-tree-paths/][https_leetcode.cn_problems_binary-tree-paths]

### 4.1 题目要求 ###

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

示例 1：  
![在这里插入图片描述][9131cc8769c24fa09ad0146eda339f3a.png]

输入：root = [1,2,3,null,5]
    输出：["1->2->5","1->3"]

示例 2：

输入：root = [1]
    输出：["1"]

提示：

树中节点的数目在范围 [1, 100] 内
    -100 <= Node.val <= 100

### 4.2 做题思路 ###

在这个题目中，我们可以使用前序遍历的方式，将路径上的所有节点的值给拼接到字符串的后面，当遇到叶子节点的时候就将这个字符串添加到集合中，然后返回，但是在返回的时候呢？我们需要将前面添加的一个节点的值给移除。

![在这里插入图片描述][adfd0bc4ef184060af5cb3468275787d.png]  
但是还不止如此，看题目我们可以发现，在节点和节点之间还需要使用 -> 来进行连接，所以我们到底什么时候移除 -> 和上一个几点的值，什么时候只是移除节点的值，如果字符串使用的是全局变量的话，回溯（恢复现场）就会比较麻烦，所以这个题目我们可以将字符串作为参数传递给函数，这样当返回的时候，这个参数就会自动回到之前的模样。

### 4.3 代码实现 ###

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
    	//全局的集合变量用来存储二叉树所有路径上的值
        List<String> list;
        public List<String> binaryTreePaths(TreeNode root) {
        
            list = new ArrayList<>();
            //因为String的拼接需要重新创建对象，速度比较慢，所以我们字符串拼接就使用StringBuilder
            dfs(root, new StringBuilder());
            return list;
        }
    
        private void dfs(TreeNode root, StringBuilder s) {
        
            if (root == null) return;
            //因为StringBuilder的变化不会因为函数的返回而恢复，所以这里我们创建一个临时的StringBuidler类
            StringBuilder sb = new StringBuilder(s);
            sb.append(root.val);
            if (root.left == null && root.right == null) {
        
                list.add(sb.toString());
                return;
            }
            //如果当前节点不是叶子节点，那么就加上->
            sb.append("->");
            dfs(root.left, sb);
            dfs(root.right, sb);
        }
    }

![在这里插入图片描述][ca82a608f3ec43b1a28af3f4b5d2bd49.png]

[ad21b455de0b4510ace6d27c2f7079b0.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/b5d95c90c28146ecb8564922101bddc6.png
[https_leetcode.cn_problems_binary-tree-pruning]: https://leetcode.cn/problems/binary-tree-pruning/
[d51ea9133d534f498cdbeee24e751a4f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/de12a68016a449bf8cc1da5798d38384.png
[92458fc3e25342d49c279ce1dabc35cb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/7af244cbd3da4913a78c4c8d4cc0f48c.png
[61cd32a87286425bbd3a55acb176fb33.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/bf839654898f48429898360d3867c89f.png
[caa66dccc65d424b85d1e360cb83e547.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/d88383fc06084f01ab1de0bcb7528de9.png
[2e3f03bc1c9e4a7c9dfb493a4d8e0c4d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/1d71b69c10a04fff82f022def91c549e.png
[3dba7be3acfa441e9e7025ba903ffb07.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/5c6039c986a542feb40c141930af528a.png
[https_leetcode.cn_problems_validate-binary-search-tree]: https://leetcode.cn/problems/validate-binary-search-tree/
[ca068a7f54f542ae8216799b7e6d6e29.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/cba50ce895c64fd793ec28a8ccc10861.png
[8b584568256f4b4992b92de6035bb7bb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/27ca642508b84406941d8f817cc4e82b.png
[92d20c3c3f8b482aacf58214dee2a376.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/47783dffd40d45cba0dc91b3b0c44364.png
[8ee5cdab39d54252aa70c7a79f91493b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/e869cce0b13147cf87388ec6e6e7d26c.png
[d502e7e1c440471b90456ca14fa4235b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/6b7fb3e6806f4d3eaa4a0b66bd685215.png
[https_leetcode.cn_problems_kth-smallest-element-in-a-bst]: https://leetcode.cn/problems/kth-smallest-element-in-a-bst/
[4f09751f310f46b7b86178f1a6d2f655.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/22303307c671496d80dc817491e7ed3e.png
[4aa57171c4ab4a9fa9f1443529222071.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/eb5c8ae7cbc141cc9fdc1eb3d74e5f5d.png
[3a8c6a6d03b541749d4341f700768f73.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/b4004498a9a949ba88fd31b163d48d75.png
[https_leetcode.cn_problems_binary-tree-paths]: https://leetcode.cn/problems/binary-tree-paths/
[9131cc8769c24fa09ad0146eda339f3a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/440f4a0839c846dd9a68dddb4e33fd4d.png
[adfd0bc4ef184060af5cb3468275787d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/53de797b675649789e78381cfdb8b4d3.png
[ca82a608f3ec43b1a28af3f4b5d2bd49.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/1e24365016254203b1da1d9396a4cf50.png