代码随想录-Day21

本文主要是介绍代码随想录-Day21，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

给你一个二叉搜索树的根节点 root ，返回树中任意两不同节点值之间的最小差值。

差值是一个正数，其数值等于两值之差的绝对值。

class Solution {int pre;int ans;public int getMinimumDifference(TreeNode root) {ans = Integer.MAX_VALUE;pre = -1;dfs(root);return ans;}public void dfs(TreeNode root) {if (root == null) {return;}dfs(root.left);if (pre == -1) {pre = root.val;} else {ans = Math.min(ans, root.val - pre);pre = root.val;}dfs(root.right);}
}

这段代码定义了一个名为 Solution 的类，其中包含两个成员变量 pre 和 ans 以及两个方法：getMinimumDifference 和 dfs。该类主要用于解决一个问题：在一棵给定的二叉搜索树（BST）中找到两个节点之间的最小差值（相邻节点间差值的最小值）。具体分析如下：

成员变量:
- pre 初始化为 -1，用于存储中序遍历过程中前一个访问到的节点的值。
- ans 初始化为 Integer.MAX_VALUE，用于记录遍历过程中找到的最小差值。
方法 getMinimumDifference(TreeNode root):
- 这是主要的接口函数，接收BST的根节点 root 作为输入参数，返回找到的最小差值。
- 首先，它初始化 ans 为 Integer.MAX_VALUE 和 pre 为 -1（虽然 pre 已经在类级别初始化，这里可视为一种明确的逻辑起点标志）。
- 然后调用深度优先搜索（DFS）方法 dfs，从根节点开始遍历整个BST。
- 最后，返回找到的最小差值 ans。
方法 dfs(TreeNode root):
- 这是一个递归方法，用于实现深度优先搜索遍历BST。
- 基本情况：如果当前节点 root 为空，则直接返回，结束当前递归路径。
- 递归遍历左子树，确保按照BST的中序遍历顺序（左根右）访问节点。
- 在访问当前节点 root 之前，先判断 pre 是否已经被初始化（即首次访问或之前已访问过节点）。如果是第一次访问（pre == -1），则将 pre 更新为当前节点值；否则，计算当前节点值与 pre 的差值，并更新全局最小差值 ans。
- 更新 pre 为当前节点值，准备与下一个节点比较。
- 递归遍历右子树，继续按照中序遍历顺序访问节点。

通过这样的中序遍历策略，由于BST的中序遍历会得到一个升序序列，遍历过程中相邻节点值的差值自然就是我们需要找的最小差值。这种方法巧妙地利用了BST的性质，实现了对最小差值的有效查找。

501. 二叉搜索树中的众数

class Solution {List<Integer> answer = new ArrayList<Integer>();int base, count, maxCount;public int[] findMode(TreeNode root) {dfs(root);int[] mode = new int[answer.size()];for (int i = 0; i < answer.size(); ++i) {mode[i] = answer.get(i);}return mode;}public void dfs(TreeNode o) {if (o == null) {return;}dfs(o.left);update(o.val);dfs(o.right);}public void update(int x) {if (x == base) {++count;} else {count = 1;base = x;}if (count == maxCount) {answer.add(base);}if (count > maxCount) {maxCount = count;answer.clear();answer.add(base);}}
}

这段代码定义了一个名为 Solution 的类，用于解决一个与二叉树相关的算法问题：找到给定二叉树中出现次数最多的元素（即众数），并返回这些众数的数组。代码主要包含类的成员变量定义、一个主方法 findMode 以及两个辅助方法 dfs 和 update。

类成员变量

List<Integer> answer：用于存储众数。
int base：记录当前处理的元素值。
int count：记录当前元素值连续出现的次数。
int maxCount：记录目前遇到的最大连续出现次数。

方法 `findMode`

功能：入口方法，用于启动查找众数的过程，接收二叉树的根节点 root 作为参数。
过程：首先调用深度优先搜索（DFS）方法遍历整个二叉树，然后将找到的所有众数存储在 answer 列表中。最后，将 answer 列表的内容转换为整型数组并返回。

方法 `dfs`

功能：递归方法，按照中序遍历（左根右）的顺序遍历二叉树。
参数：当前访问的节点 o。
过程：递归遍历左子树，然后处理当前节点（调用 update 方法），最后递归遍历右子树。

方法 `update`

功能：更新当前元素的计数，并根据计数更新众数信息。
参数：当前遍历到的元素值 x。
过程：如果当前元素值与 base 相同，则增加 count；否则，重置 count 为 1，并更新 base 为当前元素值。接着，根据 count 与 maxCount 的关系，更新 maxCount 以及众数列表 answer。

整个算法利用了二叉搜索树（BST）的中序遍历特性（遍历结果是升序序列），结合一个简单的计数逻辑来找出出现频率最高的元素。通过遍历过程中维护当前元素的出现次数以及最大出现次数，最终收集到所有的众数并返回。

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

方法一：递归

class Solution {private TreeNode ans;public Solution() {this.ans = null;}private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {if (root == null) return false;boolean lson = dfs(root.left, p, q);boolean rson = dfs(root.right, p, q);if ((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson))) {ans = root;} return lson || rson || (root.val == p.val || root.val == q.val);}public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {this.dfs(root, p, q);return this.ans;}
}

这段代码定义了一个名为 Solution 的类，用于求解二叉树中两个指定节点的最近公共祖先（Lowest Common Ancestor, LCA）。类中包含一个成员变量 ans 用于存储找到的最近公共祖先节点，以及几个方法：

构造方法 Solution()：初始化成员变量 ans 为 null。
私有方法 dfs(TreeNode root, TreeNode p, TreeNode q)：这是一个深度优先搜索（Depth First Search, DFS）方法，用于递归遍历二叉树，同时检查当前节点是否为节点 p 或 q 的祖先。它返回一个布尔值，指示以 root 为根的子树中是否包含 p 或 q。
- 如果 root 为空，返回 false，表示该子树不包含 p 或 q。
- 递归遍历左子树和右子树，获取它们是否包含 p 或 q 的信息。
- 如果当前节点的左子树和右子树中都包含了 p 和 q，或者当前节点是 p 或 q 之一，并且其子树中也包含另一个节点，那么将当前节点设置为 ans，即最近公共祖先。
- 最后，返回当前子树是否包含 p 或 q（通过 lson、rson 或当前节点值与 p、q 相等判断）。
公共方法 lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)：这是解决问题的接口方法，接收二叉树的根节点 root 以及需要查找最近公共祖先的两个节点 p 和 q。它通过调用 dfs 方法进行遍历，并返回找到的最近公共祖先节点 ans。