当前位置：首页 > ds >正文

代码随想录算法训练营第十八天

ds 2025/7/14 6:43:05

LeetCode.530 二叉搜索树的最小绝对差

题目链接二叉搜索树的最小绝对差

题解

class Solution {TreeNode pre;int result = Integer.MAX_VALUE;public int getMinimumDifference(TreeNode root) {if(root == null) return 0;find(root);return result;}public void find(TreeNode node){if(node == null) return ;find(node.left);if(pre != null) result = Math.min(result,Math.abs(node.val - pre.val));pre = node;find(node.right);}
}

解题思路

这段代码通过中序遍历（In-order Traversal）来计算二叉搜索树（BST）中任意两节点的最小绝对差。解题的核心思路是利用 BST 的中序遍历结果为有序序列的特性，相邻节点的差值即为有序数组中相邻元素的差，从而简化最小绝对差的计算。

BST 的中序遍历特性
- 对于合法的 BST，中序遍历（左 → 根 → 右）的输出是升序排列的序列。
- 例如，BST [4,2,6,1,3] 的中序遍历为 [1,2,3,4,6]，最小绝对差为 1（2-1 或 4-3）。
中序遍历计算最小差
- 使用全局变量 pre 记录中序遍历过程中的前一个节点。
- 使用全局变量 result 维护当前最小绝对差（初始化为 Integer.MAX_VALUE）。
- 在中序遍历过程中，每次访问当前节点时，计算其与前一个节点的差值的绝对值，并更新 result。
代码实现步骤
- 递归左子树：遍历左子树以确保按升序访问节点。
- 计算差值：若 pre 不为空，计算当前节点与 pre 的差值的绝对值，并更新 result。
- 更新前驱：将 pre 更新为当前节点。
- 递归右子树：继续遍历右子树。

LeetCode.501 二叉搜索树中的众数

题目链接二叉搜索树中的众数

题解

class Solution {ArrayList<Integer> resList;int maxCount;int count;TreeNode pre;public int[] findMode(TreeNode root) {resList = new ArrayList<>();maxCount = 0;count = 0;pre = null;find(root);int[] res = new int[resList.size()];for(int i = 0;i<resList.size();i++){res[i] = resList.get(i);}return res;}public void find(TreeNode root){if(root == null){return ;}find(root.left);if(pre == null || root.val != pre.val){count = 1;}else {count ++;}if(count > maxCount){resList.clear();resList.add(root.val);maxCount = count;}else if(count == maxCount){resList.add(root.val);}pre = root;find(root.right);}
}

解题思路

这段代码通过中序遍历（In-order Traversal）来查找二叉搜索树（BST）中的所有众数（出现频率最高的元素）。解题的核心思路是利用 BST 的中序遍历结果为有序序列的特性，使得相同元素会连续出现，从而简化频率统计和众数查找。

BST 的中序遍历特性
- 对于合法的 BST，中序遍历（左 → 根 → 右）的输出是升序排列的序列。
- 在升序序列中，相同元素会连续出现，便于统计每个元素的出现频率。
中序遍历统计频率
- 使用全局变量 count 记录当前元素的出现次数，maxCount 记录最大频率，pre 记录前驱节点。
- 使用 ArrayList<Integer> resList 动态存储众数（可能有多个）。
- 在中序遍历过程中：
  - 若当前节点值与前驱节点值不同，重置 count = 1。
  - 若相同，count 递增。
  - 更新 maxCount 并调整 resList：
    - 若 count > maxCount，清空 resList 并加入当前元素。
    - 若 count == maxCount，直接加入当前元素。
代码实现步骤
- 递归左子树：确保按升序访问节点。
- 频率统计：
  - 若 pre 为空或当前值与 pre 不同，重置 count = 1。
  - 否则 count++。
- 更新众数列表：
  - 若 count > maxCount，更新 maxCount 并清空 resList 后加入当前值。
  - 若 count == maxCount，直接加入当前值。
- 更新前驱：将 pre 更新为当前节点。
- 递归右子树：继续遍历右子树。

LeetCode.236 二叉树的最近公共祖先

题目链接二叉树的最近公共祖先

题解

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null) return null;if(root == p || root == q) return root;TreeNode left = lowestCommonAncestor(root.left,p,q);TreeNode right = lowestCommonAncestor(root.right,p,q);if(left != null && right != null) return root;if(left != null && right == null) return left;if(left == null && right != null) return right;return null;}
}

解题思路

这段代码用于寻找二叉树中两个节点 p 和 q 的最近公共祖先（LCA），核心思路是通过递归遍历树的左右子树，根据返回结果判断公共祖先位置：

递归终止条件：若当前节点为空，返回 null；若当前节点是 p 或 q，直接返回该节点（自身即为祖先）。
递归遍历：分别递归左子树和右子树，获取左右子树中是否包含 p 或 q 的结果（left 和 right）。
判断逻辑：
- 若 left 和 right 均不为空，说明 p 和 q 分别在当前节点的左右子树中，当前节点即为 LCA。
- 若仅 left 不为空，说明 p 和 q 都在左子树，返回 left。
- 若仅 right 不为空，说明 p 和 q 都在右子树，返回 right。
- 若两者都为空，返回 null（未找到）。