如何建一个自己的网站,dedecms 倒计时 天数 网站首页,html网站标题怎么做,黄埔网站建设设计题库链接#xff1a;https://leetcode.cn/problem-list/e8X3pBZi/ 类型题目解决方案二叉树的深搜剑指 Offer II 047. 二叉树剪枝递归#xff08;深搜#xff09;#xff1a;二叉树的后序遍历 #xff08;⭐#xff09;剑指 Offer II 048. 序列化和反序列化二叉树递归https://leetcode.cn/problem-list/e8X3pBZi/ 类型题目解决方案二叉树的深搜剑指 Offer II 047. 二叉树剪枝递归深搜二叉树的后序遍历 ⭐剑指 Offer II 048. 序列化和反序列化二叉树递归深搜二叉树的前序遍历⭐剑指 Offer II 049. 从根节点到叶节点的路径数字之和递归深搜二叉树的前序遍历⭐剑指 Offer II 050. 向下的路径节点值之和递归深搜二叉树的前序遍历⭐剑指 Offer II 051. 节点值之和最大的路径递归深搜二叉树的后序遍历⭐二叉搜索树剑指 Offer II 052. 展平二叉搜索树栈 二叉树中序遍历⭐剑指 Offer II 053. 二叉搜索树的下一个节点中序遍历二叉搜索树的特性⭐剑指 Offer II 054. 所有大于或等于节点的值之和倒序的中序遍历⭐剑指 Offer II 055. 二叉搜索树迭代器二叉搜索树中序遍历过程拆分⭐剑指 Offer II 056. 二叉搜索树中两个节点的值之和中序遍历 HashSet⭐TreeSet 和 TreeMap 的应用剑指 Offer II 057. 值和下标之差都在给定的范围内平衡二叉搜索树TreeSet ⭐剑指 Offer II 058. 日程表平衡二叉搜索树TreeMap⭐ 二叉树是一种典型的具有递归性质的数据结构二叉树的广度优先搜索通常是通过队列来实现而二叉树的深度优先搜索可以分为中序遍历、前序遍历和后序遍历。二叉树 DFS 的递归写法非常简单按照遍历的顺序编写递归顺序即可而将递归代码改写成迭代的形式则通常需要 栈 来辅助栈主要用于二叉树左侧节点的存储。 …… 而二叉搜索树则是一种特殊的二叉树在二叉搜索树中进行搜索、添加和删除操作的平均时间复杂度均为 O(logn)如果按照中序遍历的顺序遍历一棵二叉搜索树那么则会按照从小到大的顺序依次遍历每个节点。由于这个特性与二叉搜索树相关的很多面试题都适合使用中序遍历解决。 …… 在 Java 中提供了 TreeSet 和 TreeMap 这两种实现了平衡二叉搜索树的数据结构如果需要动态地在一个排序的数据集合中添加元素或者需要根据数据的大小查找那么可以使用 TreeSet 和 TreeMap 解决。 常用方法 ceiling()返回键大于或等于给定值的最小键如果没有则返回 nullfloor()返回键小于或等于给定值的最大键如果没有则返回 nullhigher()返回键大于给定值的最小键如果没有则返回 nulllower()返回键小于给定值的最大键如果没有则返回 null 1. 剑指 Offer II 047. 二叉树剪枝 – P132 给定一个二叉树 根节点 root 树的每个节点的值要么是 0要么是 1。请剪除该二叉树中所有节点的值为 0 的子树。 节点 node 的子树为 node 本身以及所有 node 的后代。 1.1 递归深搜二叉树的后序遍历 – O(n)⭐
时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( h ) O(h) O(h) Key二叉树的后序遍历左、右、根一般我们可以用递归深搜来实现二叉树的遍历适用于小树深的情况而如果是大树深则更推荐采用迭代的方式用栈来保存路径。 /*** 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 {// Solution1二叉树后序遍历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 root.val 0) {return null; // 将左、右子节点为null, 且自身值为0的节点剪枝}return root;}
}2. 剑指 Offer II 048. 序列化和反序列化二叉树 – P134 序列化是将一个数据结构或者对象转换为连续的比特位的操作进而可以将转换后的数据存储在一个文件或者内存中同时也可以通过网络传输到另一个计算机环境采取相反方式重构得到原数据。 …… 请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。 2.1 递归深搜二叉树的前序遍历 – O(n)⭐
时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( h ) O(h) O(h) 如何将二叉树序列化成一个字符串 前序遍历每一个节点用分隔符对不同的节点进行分隔把 null 节点序列化成一个特殊的字符串如 ”#“ …… 反序列化则是 将序列化形成的字符串按分隔符进行分割”#“ 与 null 对应递归还原节点 …… 细节方法传参时传递的是一个只有一个元素的数组来作为字符串遍历的下标。 /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }*/
public class Codec {// Encodes a tree to a single string.public String serialize(TreeNode root) {if (root null) return #;String left serialize(root.left);String right serialize(root.right);return String.valueOf(root.val) , left , right;}// Decodes your encoded data to tree.public TreeNode deserialize(String data) {String[] strs data.split(,);int[] i {0}; // 细节变量传参不会改变值因此要用数组传参return dfs(strs, i);}public TreeNode dfs(String[] strs, int[] i) {String str strs[i[0]];i[0];if (str.equals(#)) return null;TreeNode node new TreeNode(Integer.parseInt(str));node.left dfs(strs, i);node.right dfs(strs, i);return node;}
}// Your Codec object will be instantiated and called as such:
// Codec ser new Codec();
// Codec deser new Codec();
// TreeNode ans deser.deserialize(ser.serialize(root));3. 剑指 Offer II 049. 从根节点到叶节点的路径数字之和 – P136 给定一个二叉树的根节点 root 树中每个节点都存放有一个 0 到 9 之间的数字。 每条从根节点到叶节点的路径都代表一个数字 例如从根节点到叶节点的路径 1 - 2 - 3 表示数字 123 。 计算从根节点到叶节点生成的 所有数字之和 。 叶节点 是指没有子节点的节点。 3.1 递归深搜二叉树的前序遍历 – O(n)⭐
时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( h ) O(h) O(h) Key二叉树中路径相关的面试题通常都可以使用深度优先搜索的方法解决这是因为路径通常顺着指向子节点的指针的方向也就是纵向方法。 /*** 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 {// Solution1二叉树前序遍历记录路径public int sumNumbers(TreeNode root) {return dfs(root, 0);}public int dfs(TreeNode root, int path) {if (root null) return 0;path path * 10 root.val; // 记录路径if (root.left null root.right null) return path;return dfs(root.left, path) dfs(root.right, path);}
}4. 剑指 Offer II 050. 向下的路径节点值之和 – P136 给定一个二叉树的根节点 root 和一个整数 targetSum 求该二叉树里节点值之和等于 targetSum 的 路径 的数目。 路径 不需要从根节点开始也不需要在叶子节点结束但是路径方向必须是向下的只能从父节点到子节点。 4.1 递归深搜二叉树的前序遍历 – O(n)⭐
时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( h ) O(h) O(h) Keypath 用于记录从根节点出发所经过的路径map 用于记录累加路径和出现的次数遍历所有的节点在这个过程中 path - target 在map 中出现的次数即为二叉树中节点值之和等于 target 的路径的数目。 /*** 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 pathSum(TreeNode root, int targetSum) {MapLong, Integer map new HashMap(); // Node.val 109, 相加有可能数值溢出map.put(0L, 1); // 赋初值path - target return dfs(root, targetSum, map, 0);}public int dfs(TreeNode root, int target, MapLong, Integer map, long path) {if (root null) return 0;path root.val;int count map.getOrDefault(path-target, 0); // 查询当前路径下是否存在符合条件的子路径map.put(path, map.getOrDefault(path,0)1); // 记录当前路径count dfs(root.left, target, map, path); // 向左遍历count dfs(root.right, target, map, path); // 向右遍历map.put(path, map.get(path)-1); // 删除当前路径节点回到上一路径状态return count;}
}5. 剑指 Offer II 051. 节点值之和最大的路径 – P139 路径 被定义为一条从树中任意节点出发沿父节点-子节点连接达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点且不一定经过根节点。 路径和 是路径中各节点值的总和。 给定一个二叉树的根节点 root 返回其 最大路径和即所有路径上节点值之和的最大值。 5.1 递归深搜二叉树的后序遍历 – O(n)⭐
时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( h ) O(h) O(h) Key原书题解太过麻烦推荐 【灵茶山艾府】彻底掌握直径 DP从二叉树到一般树Python/Java/C/Go重点是要理解递归思想递归就像是一个后入先出的栈一层层递归返回。 /*** 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 res Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {dfs(root);return res;}public int dfs(TreeNode root) {if (root null) return 0;int left dfs(root.left); // 左子树最大链和int right dfs(root.right); // 右子树最大链和res Math.max(res, left right root.val); // 两条链拼成路径return Math.max(Math.max(left, right) root.val, 0); // 路径和为负数则不选}
}6. 剑指 Offer II 052. 展平二叉搜索树 – P142 给你一棵二叉搜索树请 按中序遍历 将其重新排列为一棵递增顺序搜索树使树中最左边的节点成为树的根节点并且每个节点没有左子节点只有一个右子节点。 6.1 栈 二叉树中序遍历 – O(n)⭐
时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( n ) O(n) O(n) 以中序遍历的顺序递增式的遍历每个节点并在遍历的过程中改变节点的指向。 /*** 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 {// Solution1二叉树中序遍历public TreeNode increasingBST(TreeNode root) {StackTreeNode sk new Stack();TreeNode cur root; // 当前节点TreeNode prev null; // 前一节点TreeNode head null; // 展开后的首节点while (cur ! null || !sk.isEmpty()) {while (cur ! null) { // 将以当前节点为首的左侧节点全部入栈sk.push(cur);cur cur.left;}cur sk.pop(); // 左侧节点以此出栈if (prev ! null) { prev.right cur;} else {head cur; // 如果prev为null说明此时出栈的节点是展开后的头节点}prev cur;cur.left null;cur cur.right; // 继续遍历}return head;}
}7. 剑指 Offer II 053. 二叉搜索树的下一个节点 – P144 给定一棵二叉搜索树和其中的一个节点 p 找到该节点在树中的中序后继。如果节点没有中序后继请返回 null 。 节点 p 的后继是值比 p.val 大的节点中键值最小的节点即按中序遍历的顺序节点 p 的下一个节点。 7.1 中序遍历二叉搜索树的特性 – O(h)⭐
时间复杂度 O ( h ) O(h) O(h)空间复杂度 O ( 1 ) O(1) O(1) 该题最直观的思路就是采用二叉树的中序遍历逐一遍历二叉树的每个节点。但由于本题是二叉搜索树因此我们可以利用二叉搜索树的特性每当到达一个节点就比较根节点的值和节点 p 的值如果当前节点的值比节点 p 的值大我们就暂存其节点并向其左孩子遍历如果当前节点的值比节点 p 的值要小那么我们就向其右孩子遍历直至找到所有比 p 节点值大的节点中值最小的那一个。 /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }*/
class Solution {public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {TreeNode cur root;TreeNode res null; // 返回结果while (cur ! null) {if (cur.val p.val) {res cur;cur cur.left; // 当前节点值大于p节点值暂存当前节点并寻找大于p节点值中最小的节点} else {cur cur.right;}}return res; }
}8. 剑指 Offer II 054. 所有大于或等于节点的值之和 – P146 给定一个二叉搜索树请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。 提醒一下二叉搜索树满足下列约束条件 节点的左子树仅包含键 小于 节点键的节点。节点的右子树仅包含键 大于 节点键的节点。左右子树也必须是二叉搜索树。 8.1 倒序的中序遍历 – O(n)⭐
时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( h ) O(h) O(h) Key二叉搜索树的中序遍历按照节点值从小到大按顺序遍历也就是当遍历到某个节点时比该节点小的节点都已经遍历过了而本题要求的是将每个节点的值替换成树中大于或者等于该节点值的所有节点值之和因此可以倒序中序遍历从右 根 左的顺序从大到小进行遍历这样就保证了只需一次遍历即可求出节点值的和。当然了我们也可以通过两次遍历第一次先求出所有节点值的和第二次依次遍历用 total - sum 得到需要的值 /*** 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 {// Soultion1倒序的中序遍历右 根 左public TreeNode convertBST(TreeNode root) {StackTreeNode sk new Stack();TreeNode cur root;int sum 0;while (cur ! null || !sk.isEmpty()) {while (cur ! null) {sk.push(cur);cur cur.right;}cur sk.pop();sum cur.val;cur.val sum;cur cur.left;}return root;}
}9. 剑指 Offer II 055. 二叉搜索树迭代器 – P148 实现一个二叉搜索树迭代器类BSTIterator 表示一个按中序遍历二叉搜索树BST的迭代器 BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字且该数字小于 BST 中的任何元素。boolean hasNext() 如果向指针右侧遍历存在数字则返回 true 否则返回 false 。int next()将指针向右移动然后返回指针处的数字。 …… 注意指针初始化为一个不存在于 BST 中的数字所以对 next() 的首次调用将返回 BST 中的最小元素。 9.1 二叉搜索树中序遍历过程拆分 – O(1)⭐
时间复杂度 O ( 1 ) O(1) O(1)空间复杂度 O ( h ) O(h) O(h) 该题根据不同的限制条件有不同的解法如 可以改变输入的二叉树结构那么我们就可以将二叉搜索树展平相当于对链表的遍历如果不可以改变输入的二叉树结构那么我们可以在二叉搜索树遍历的时候用链表将节点记录下来这样的缺点就是需要使用额外的存储结构如果不可以改变输入的二叉树结构且不能使用额外的存储空间拆分二叉搜素树中序遍历的过程也是可以的我们需要理解 二叉搜索树中序遍历 本身的外循环判断条件就可以作为 hasNext 的判断然后通过 next 每调用一次进行一次循环遍历即可。 /*** 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 BSTIterator {TreeNode cur;StackTreeNode sk;public BSTIterator(TreeNode root) { // 构造函数输入二叉搜索树的根节点初始化该迭代器cur root;sk new Stack();}public int next() { // 返回二叉搜索树中下一个最小的节点的值while (cur ! null) {sk.push(cur);cur cur.left;}cur sk.pop();int val cur.val;cur cur.right;return val;}public boolean hasNext() { // 返回二叉搜索树是否还有下一个节点return cur ! null || !sk.isEmpty();}
}/*** Your BSTIterator object will be instantiated and called as such:* BSTIterator obj new BSTIterator(root);* int param_1 obj.next();* boolean param_2 obj.hasNext();*/10. 剑指 Offer II 056. 二叉搜索树中两个节点的值之和 – P150 给定一个二叉搜索树的 根节点 root 和一个整数 k , 请判断该二叉搜索树中是否存在两个节点它们的值之和等于 k 。假设二叉搜索树中节点的值均唯一。 10.1 中序遍历 HashSet – O(n)⭐
时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( n ) O(n) O(n) Key该题可以看成二叉树版的两数之和常规做法就是通过顺序遍历找出该数据结构中的数据是否存在 target - cur.val如果存在则说明该数据结构中存在两数之和等于 target后序进阶可能会要求输出符合条件的两数的下标值改用 HashMap 在记录值的同时存储下标即可解决。 …… Ps当然以上做法并未考虑二叉搜索树这一要素如想进一步优化我们可以利用二叉搜素树的特点将时间复杂度降低至 O(h)通过数组双指针的策略来进行数据的遍历但需要编写专门的二叉搜索树迭代器正序和倒序都需要。 /*** 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 findTarget(TreeNode root, int k) {SetInteger st new HashSet();DequeTreeNode sk new ArrayDeque(); // stack换成Deque可以提高速度TreeNode cur root;while (cur ! null || !sk.isEmpty()) { // 中序遍历while (cur ! null) {sk.push(cur);cur cur.left;}cur sk.pop();if (st.contains(k-cur.val)) { // 常规套路两数之和return true;}st.add(cur.val); // 记录每一次遍历到的值cur cur.right;} return false;}
}11. 剑指 Offer II 057. 值和下标之差都在给定的范围内 – P155 给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j使得 abs(nums[i] - nums[j]) t 同时又满足 abs(i - j) k 。 如果存在则返回 true不存在返回 false。 11.1 平衡二叉搜索树TreeSet – O(nlogn)⭐
时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)空间复杂度 O ( n ) O(n) O(n) Key该题最常规的做法就是遍历所有数字然后每遍历到一个数字就判断该数字的前 k 个数字与其差的绝对值是否小于等于 t这种方法的时间复杂度为 O(nk)。 …… 除以上方法外还有一种巧妙的方法可以时间复杂度降低至 O(n)此时我们需要借助 HashMap并通过给遍历的每个数字划分桶号这里我们可以理解为数据范围0-t 范围入 0 桶t1 - 2t1范围入 1 桶以此类推这样我们只要找到一个桶中有两个数即可判断是否有数字满足条件如果没有我们还可以查看当前数字所在桶的前后两桶中是否有数字可以和当前数字组合满足条件循环遍历一遍即可解决问题。 …… 本题下方给出的代码属于另一种方法属于对 TreeSet 性质的运用通过 TreeSet 我们可以以 O(logn) 的时间复杂度得出一个数字对应集合中 ≥的最小值以及 ≤的最大值对这两个数字进行判断即可得出当前数字与其前 k 个数字之间的一个数据范围然后得出答案。 class Solution {public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {TreeSetLong set new TreeSet(); // 注意包装类应选择Longint有溢出风险for (int i 0; i nums.length; i) {Long lower set.floor((long)nums[i]); // 下取值找小最大if (lower ! null nums[i] - lower t) return true;Long higher set.ceiling((long)nums[i]); // 上取值找大最小if (higher ! null higher - nums[i] t) return true;set.add((long) nums[i]);if (i k) { // 移除多余数值set只保留当前数字的前k个数值set.remove((long)nums[i-k]);}}return false;}
}12. 剑指 Offer II 058. 日程表 – P157 请实现一个 MyCalendar 类来存放你的日程安排。如果要添加的时间内没有其他安排则可以存储这个新的日程安排。 MyCalendar 有一个 book(int start, int end)方法。它意味着在 start 到 end 时间内增加一个日程安排注意这里的时间是半开区间即 [start, end), 实数 x 的范围为 start x end。 当两个日程安排有一些时间上的交叉时例如两个日程安排都在同一时间内就会产生重复预订。 每次调用 MyCalendar.book方法时如果可以将日程安排成功添加到日历中而不会导致重复预订返回 true。否则返回 false 并且不要将该日程安排添加到日历中。 12.1 平衡二叉搜索树TreeMap – O(nlogn)⭐
时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)空间复杂度 O ( n ) O(n) O(n) 常规方法直接遍历通过 ArrayListint[] 对数据进行存储每次 book(start, end) 操作都会对 ArrayList 进行一次遍历比较当前事件是否与已经存在的事件之间存在冲突如果冲突返回 false无冲突则将当前事件加入到集合中并返回 true。 …… 利用二叉搜索树的特性使用 TreeSet 或 TreeMap 对数据进行存储利用其特有的 API — floorEntry() / ceilEntry() 找出小最大和大最小然后与当前事件的时间范围进行比较即可节省了比较次数。 …… 还可以使用线段树的方法详细内容可参考方法三线段树 TreeMap 实现的接口、继承的类如下图所示
class MyCalendar {TreeMapInteger,Integer map; // 写成 Map 不行会出现 error: cannot find symbol [in MyCalendar.java] 错误这是因为其中的floorEntry()以及ceilingEntry()方法是源自于public interface NavigableMapK,V接口的。public MyCalendar() {map new TreeMap();}public boolean book(int start, int end) {Map.EntryInteger,Integer event map.floorEntry(start); // 下取值找到比当前开始时间低的最近的开始事件if (event ! null event.getValue() start) return false; // 判断找到的事件的结束时间是否超过了当前的开始时间event map.ceilingEntry(start); // 上取值找到比当前开始时间高的最近开始事件if (event ! null event.getKey() end) return false; // 判断找到的事件的开始时间是否早于当前的结束时间map.put(start, end); // 都没有则说明当前事件符合要求可以放入集合return true;}
}
/*** Your MyCalendar object will be instantiated and called as such:* MyCalendar obj new MyCalendar();* boolean param_1 obj.book(start,end);*/13. 继续提升加练题目 可参考 树 · SharingSource/LogicStack-LeetCode Wiki · GitHub二叉树 · SharingSource/LogicStack-LeetCode Wiki · GitHub线段树 · SharingSource/LogicStack-LeetCode Wiki · GitHub
