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

代码随想录算法训练营第二十一天 | 530.二叉搜索树的最小绝对差、501.二叉搜索树中的众数、236. 二叉树的最近公共祖先

news 来源：原创 2024/7/5 0:38:26

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

题目链接：https://leetcode.cn/problems/minimum-absolute-difference-in-bst/
文档讲解：https://programmercarl.com/0530.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E7%BB%9D%E5%AF%B9%E5%B7%AE.html
视频讲解：https://www.bilibili.com/video/BV1DD4y11779

思路

使用了中序遍历的递归法，因为中序遍历出来是一个递增的数组，然后计算每一个差值，找到差值的最小值。
在计算差值时，用双指针进行遍历。

代码

class Solution {int min = Integer.MAX_VALUE;TreeNode pre;public int getMinimumDifference(TreeNode root) {getMin(root);return min;}public void getMin(TreeNode root) {int res;if (root == null) return;getMin(root.left);if (pre != null) {res = Math.abs(pre.val - root.val);min = Math.min(res, min);}pre = root;// 将pre的值移到root上，保存了上一个节点。getMin(root.right);}}

501.二叉搜索树中的众数

题目链接：https://leetcode.cn/problems/find-mode-in-binary-search-tree/
文档讲解：https://programmercarl.com/0501.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E4%BC%97%E6%95%B0.html
视频讲解：https://www.bilibili.com/video/BV1fD4y117gp

思路

还是用中序遍历来得到一个递增的数组。用双指针来记录上一个节点和当前节点，避免使用额外空间。
在中的逻辑中，如果pre为空，说明前面没有节点，将count置为1；如果pre和root的值相等，将count加一；如果不相等，就将count置为1。
然后判断当前count和maxCount之间的关系，如果count大，就更新maxCount的值，并且清空之前的数组，加入当前值。如果相等，直接把当前值加入数组。

代码

class Solution {List<Integer> nums = new ArrayList<>();TreeNode pre;int maxCount = 0, count = 0;public int[] findMode(TreeNode root) {getModeNum(root);int[] res = new int[nums.size()];for (int i = 0; i < nums.size(); i++) {res[i] = nums.get(i);}return res;}public void getModeNum(TreeNode root){if (root == null) return;getModeNum(root.left); // 左// 中if (pre == null) count = 1;else if (pre.val == root.val) count++;else if (pre.val != root.val) count = 1;pre = root;if (count == maxCount) nums.add(root.val);else if (count > maxCount) {maxCount = count;nums.clear();nums.add(root.val);}getModeNum(root.right); // 右}
}

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

题目链接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
文档讲解：https://programmercarl.com/0236.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88.html
视频讲解：https://www.bilibili.com/video/BV1jd4y1B7E2

思路

用后序遍历，能体现回溯的思路，左右节点传回包含p或q的节点。
- 如果某个节点的左右节点都有值，说明左右都包含p和q，那么该节点就是最近公共祖先；
- 如果只有左节点有值，就把左节点向上返回；如果只有右节点有值，就把左节点向上返回；
- 当节点为空或等于p或q，就返回当前节点，递归结束。

代码

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