代码随想录-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）中找到两个节点之间的最小差值（相邻节点间差值的最小值）。具体分析如下：

1. 成员变量:

   • pre 初始化为 -1，用于存储中序遍历过程中前一个访问到的节点的值。
   • ans 初始化为 Integer.MAX_VALUE，用于记录遍历过程中找到的最小差值。

2. 方法 getMinimumDifference(TreeNode root):

   • 这是主要的接口函数，接收BST的根节点 root 作为输入参数，返回找到的最小差值。
   • 首先，它初始化 ans 为 Integer.MAX_VALUE 和 pre 为 -1（虽然 pre 已经在类级别初始化，这里可视为一种明确的逻辑起点标志）。
   • 然后调用深度优先搜索（DFS）方法 dfs，从根节点开始遍历整个BST。
   • 最后，返回找到的最小差值 ans。

3. 方法 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 用于存储找到的最近公共祖先节点，以及几个方法：

1. 构造方法 Solution()：初始化成员变量 ans 为 null。
2. 私有方法 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 相等判断）。
3. 公共方法 lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)：这是解决问题的接口方法，接收二叉树的根节点 root 以及需要查找最近公共祖先的两个节点 p 和 q。它通过调用 dfs 方法进行遍历，并返回找到的最近公共祖先节点 ans。

总之，这段代码实现了一个在二叉树中寻找两个指定节点最近公共祖先的算法，利用了深度优先搜索和递归的思想。通过遍历树并利用递归返回的信息，能够有效确定并返回最近公共祖先节点。

这篇关于代码随想录-Day21的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---