【算法系列篇】递归、搜索和回溯（三）-阿里云开发者社区

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

2024-01-29 79

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

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

前言

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

什么是二叉树剪枝

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

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

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

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

1. 二叉树剪枝

https://leetcode.cn/problems/binary-tree-pruning/

1.1 题目要求

给你二叉树的根结点 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

/**
 * 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 {
    public TreeNode pruneTree(TreeNode root) {
    }
}

1.2 做题思路

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

1.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 {
    public TreeNode pruneTree(TreeNode root) {
        if (root == null) return null;
        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);
        if (root.left == null && root.right == null) {
            if (root.val == 0) root = null;
        }
        return root;
    }
}

2. 验证二叉搜索树

https://leetcode.cn/problems/validate-binary-search-tree/

2.1 题目要求

给你一个二叉树的根节点 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

/**
 * 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 {
    public boolean isValidBST(TreeNode root) {
    }
}

2.2 做题思路

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

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

2.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 {
    long prev = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        boolean l = isValidBST(root.left);
        if (l == false) return false;
        if (root.val > prev) prev = root.val;
        else return false;
        boolean r = isValidBST(root.right);
        return l && r;
    }
}

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

https://leetcode.cn/problems/kth-smallest-element-in-a-bst/

3.1 题目要求

给定一个二叉搜索树的根节点 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 <= 104
0 <= Node.val <= 104

/**
 * 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 {
    public int kthSmallest(TreeNode root, int k) {
    }
}

3.2 做题思路

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

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

3.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 {
    int count, ret;
    public int kthSmallest(TreeNode root, int k) {
        count = k;
        dfs(root);
        return ret;
    }
    private void dfs(TreeNode root) {
        if (count == 0 || root == null) return;
        dfs(root.left);
        count--;
        if (count == 0) {
            ret = root.val;
            return;
        }
        dfs(root.right);
    }
}

4. 二叉树的所有路径

https://leetcode.cn/problems/binary-tree-paths/

4.1 题目要求

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

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

示例 1：

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

示例 2：

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

提示：

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

/**
 * 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 {
    public List<String> binaryTreePaths(TreeNode root) {
    }
}

4.2 做题思路

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

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

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);
    }
}

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

前言

什么是二叉树剪枝

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 代码实现

热门文章

最新文章

相关课程

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

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

前言

什么是二叉树剪枝

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 代码实现

热门文章

最新文章

相关课程

相关电子书

相关实验场景