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

前言

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

什么是二叉树剪枝

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

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