【每日力扣】修剪二叉搜索树与复原 IP 地址

本文主要是介绍【每日力扣】修剪二叉搜索树与复原 IP 地址，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

🔥 个人主页: 黑洞晓威
😀你不必等到非常厉害，才敢开始，你需要开始，才会变的非常厉害。

669. 修剪二叉搜索树

给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。可以证明，存在 唯一的答案 。

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

解决思路

如果当前节点为空，则直接返回空节点。
如果当前节点值小于最小边界，则修剪掉当前节点的左子树，并递归处理右子树。
如果当前节点值大于最大边界，则修剪掉当前节点的右子树，并递归处理左子树。
如果当前节点值在范围内，则修剪左右子树，并保持当前节点不变。

代码

class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int val) {this.val = val;}
}public class TrimBST {public TreeNode trimBST(TreeNode root, int low, int high) {if (root == null) {return null;}if (root.val < low) {// 如果根节点值小于最小边界，则修剪掉左子树，并递归处理右子树return trimBST(root.right, low, high);} else if (root.val > high) {// 如果根节点值大于最大边界，则修剪掉右子树，并递归处理左子树return trimBST(root.left, low, high);} else {// 根节点值在边界内，则修剪左右子树，并保持根节点不变root.left = trimBST(root.left, low, high);root.right = trimBST(root.right, low, high);return root;}}public static void main(String[] args) {TreeNode root = new TreeNode(3);root.left = new TreeNode(0);root.right = new TreeNode(4);root.left.right = new TreeNode(2);root.left.right.left = new TreeNode(1);int low = 1;int high = 3;TrimBST solution = new TrimBST();TreeNode result = solution.trimBST(root, low, high);// 输出结果System.out.println(result);}
}

复原 IP 地址

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

例如："0.1.2.201" 和 "192.168.1.1" 是有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你不能重新排序或删除 s 中的任何数字。你可以按任何顺序返回答案。

解决思路

对于这个问题，我们可以使用回溯算法来生成所有可能的 IP 地址。具体步骤如下：

创建一个结果列表，用于存储所有有效的 IP 地址。
开始回溯搜索，遍历可能的 IP 地址格式。
在每一步中，判断当前的子串是否是合法的 IP 地址段（在 0 到 255 之间，且不能含有前导 0）。
如果满足条件，则继续递归搜索下一段 IP 地址。
如果四段 IP 地址都满足条件，并且已经遍历完整个字符串 s，则将当前的 IP 地址添加到结果列表中。

代码

import java.util.ArrayList;
import java.util.List;public class RestoreIPAddress {public List<String> restoreIpAddresses(String s) {List<String> result = new ArrayList<>();backtrack(s, 0, new ArrayList<>(), result);return result;}private void backtrack(String s, int start, List<String> path, List<String> result) {if (path.size() == 4 && start == s.length()) {result.add(String.join(".", path));return;}for (int i = 1; i <= 3; i++) {if (start + i > s.length()) {break;}String segment = s.substring(start, start + i);if (isValid(segment)) {path.add(segment);backtrack(s, start + i, path, result);path.remove(path.size() - 1);}}}private boolean isValid(String segment) {if (segment.length() > 1 && segment.charAt(0) == '0') {return false; // 不允许前导 0}int num = Integer.parseInt(segment);return num >= 0 && num <= 255;}public static void main(String[] args) {String s = "25525511135";RestoreIPAddress solution = new RestoreIPAddress();List<String> result = solution.restoreIpAddresses(s);System.out.println(result); // 输出 ["255.255.11.135","255.255.111.35"]}
}