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

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

题目：
给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。

解题思路：
由于二叉搜索树的中序遍历是有序的，因此可以通过中序遍历逐步比较当前节点和前一个节点的值，更新最小差值。具体步骤如下：

1. 初始化结果变量 res 为最大整数值，前一个节点 pre 为 null。
2. 使用中序遍历对二叉搜索树进行递归遍历。
3. 在中序遍历过程中，如果前一个节点 pre 不为空，则计算当前节点与 pre 节点值的差，并更新最小差值 res。
4. 将当前节点更新为 pre，继续遍历。
5. 最后，返回 res 即为最小绝对差。

代码：

class Solution {private int res = Integer.MAX_VALUE;private TreeNode pre = null;public int getMinimumDifference(TreeNode root) {helper(root);return res;}public void helper(TreeNode root){if (root==null){return;}helper(root.left);if(pre!=null){res = Math.min(res,root.val-pre.val);}pre = root;helper(root.right);}
}

501. 二叉搜索树中的众数

题目：
给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。

解题思路：
由于二叉搜索树的中序遍历是递增有序的，可以通过中序遍历来找到所有的众数。具体步骤如下：

1. 变量初始化：

   • 使用 maxCount 来记录出现次数的最大值。
   • count 记录当前节点值的出现次数。
   • pre 用于存储上一个访问的节点，以便判断当前节点是否与前一个节点的值相同。

2. 中序遍历：

   • 使用递归的中序遍历访问二叉搜索树的每个节点。
   • 如果当前节点的值与前一个节点相同，则增加 count。
   • 如果不同，则将 count 重置为 1。

3. 更新众数列表：

   • 当 count 大于 maxCount 时，清空 modeList，更新 maxCount，并将当前值加入 modeList。
   • 如果 count 等于 maxCount，则直接将当前值添加到 modeList。

4. 返回结果：
   遍历完成后，将 modeList 转换为数组并返回。

代码：

class Solution {List<Integer> modeList = new ArrayList<>();private int maxCount = 0;private int count = 0;private TreeNode pre = null;public int[] findMode(TreeNode root) {if (root == null) {return new int[0];}helper(root);int[] res = new int[modeList.size()];for (int i = 0; i < modeList.size(); i++) {res[i] = modeList.get(i);}return res;}public void helper(TreeNode root) {if (root == null) {return;}helper(root.left);// 更新当前节点的出现次数if (pre != null && pre.val == root.val) {count++;} else {count = 1;}// 更新 maxCount 和 modeListif (count > maxCount) {modeList.clear();maxCount = count;modeList.add(root.val);} else if (count == maxCount) {modeList.add(root.val);}pre = root;  // 更新 pre 为当前节点helper(root.right);}}

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

题目：
给定一个二叉树，找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

解题思路：
可以通过递归的方式查找两个节点的最近公共祖先。具体思路分为两种方法：

1. 方法一：后序遍历递归查找，并利用布尔值返回节点位置。

   • 使用递归函数 helper 遍历树的每个节点。
   • 定义 left、right 和 mid 分别表示左子树、右子树是否包含 p 或 q，以及当前节点是否是 p 或 q。
   • 当满足 (left && right) || (mid && left) || (mid && right) 时，当前节点为最近公共祖先，将其存入 node。
   • 递归返回 mid || left || right，表示当前子树中是否包含 p 或 q。

2. 方法二：递归分治法。

   • 从根节点开始递归查找 p 和 q。
   • 如果当前节点为空或等于 p 或 q，则直接返回当前节点。
   • 递归查找左右子树，若 p 和 q 分别位于左右子树，则当前节点为最近公共祖先。
   • 如果 p 和 q 都在左子树或右子树中，则返回找到的子树根节点。

代码：

class Solution {private TreeNode node = null;public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root==null){return null;}boolean res = helper(root,p,q);return node;}public boolean helper(TreeNode root, TreeNode p, TreeNode q) {if(root==null){return false;}boolean left = helper(root.left,p,q);boolean right = helper(root.right,p,q);boolean mid = (root == p || root == q);if(left && right || left && mid || right && mid){node = root;}return mid || right || left;}
}

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root == null || 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) { // 若未找到节点 p 或 qreturn null;}else if(left == null && right != null) { // 若找到一个节点return right;}else if(left != null && right == null) { // 若找到一个节点return left;}else { // 若找到两个节点return root;}}
}