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

2023-12-14 16:38:55

在这里插入图片描述

前言

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

什么是二叉树剪枝

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

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

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

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

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

在这里插入图片描述

文章来源:https://blog.csdn.net/m0_73888323/article/details/134981933
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。