h5网站开发教程,一个微信小程序需要多少钱,wordpress首页添加友情,wordpress发文章摘要#x1f525; 个人主页: 黑洞晓威 #x1f600;你不必等到非常厉害#xff0c;才敢开始#xff0c;你需要开始#xff0c;才会变的非常厉害。 669. 修剪二叉搜索树
给你二叉搜索树的根节点 root #xff0c;同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树 个人主页: 黑洞晓威 你不必等到非常厉害才敢开始你需要开始才会变的非常厉害。 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.1681.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 ListString restoreIpAddresses(String s) {ListString result new ArrayList();backtrack(s, 0, new ArrayList(), result);return result;}private void backtrack(String s, int start, ListString path, ListString 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();ListString result solution.restoreIpAddresses(s);System.out.println(result); // 输出 [255.255.11.135,255.255.111.35]}
}
