【随想录】Day21—第六章 二叉树part07

本文主要是介绍【随想录】Day21—第六章 二叉树part07，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

题目1: 530. 二叉搜索树的最小绝对差

• 题目链接：530. 二叉搜索树的最小绝对差

---

1- 思路

中序遍历，将遍历结果收集到数组中

• 遍历数组，求解数组两个元素之间的差值

---

2- 题解

⭐ 二叉搜索树的最小绝对差 ——题解思路

class Solution {List<Integer> res = new ArrayList<>();public int getMinimumDifference(TreeNode root) {inorder(root);int[] nums = new int[res.size()];for(int i = 0 ; i < nums.length;i++){nums[i] = res.get(i);}int min = 999999;for(int i = 1 ; i < nums.length;i++){int tmp = nums[i] - nums[i-1];if(tmp<min){min = tmp;}}return min;}public void inorder(TreeNode root){if(root==null){return;}inorder(root.left);res.add(root.val);inorder(root.right);}
}

---

题目2: 二叉搜索树中的众数

• 题目链接：501. 二叉搜索树中的众数

---

1- 思路

使用递归实现二叉搜索树中的众数
在二叉树：搜索树的最小绝对差中我们就使用了pre指针和cur指针的技巧，这次又用上了。
技巧：

• 1. 利用 cur 和 pre 指针
• 2. pre 记录 cur 的前一个值：由于是递归，且是中序的顺序，因此可以理解为从 BST 的左下角的结点开始
• 3. 递归三部曲
  • 3.1 终止条件：遇到 null 则返回
  • 3.2 单层递归：
  • 对 count 计数
    • 采用中序遍历，左 中 右 的顺序，中的判断：如果 pre 为 null 或者 pre 和 cur 的值不相等，则 count 归 1 重新开始计数。
  • **更新 count **
    • 如果当前 count 大于 maxCount 证明需要对 maxCount 更新，且 res 结果集需要清空，且加入当前 值
    • 如果 count == maxCount ，证明此时找到了结果，收集结果
    • 最终移动 pre

public void findMode1(TreeNode root) {if (root == null) {return;}findMode1(root.left);int rootValue = root.val;// 计数if (pre == null || rootValue != pre.val) {count = 1;} else {count++;}// 更新结果以及maxCountif (count > maxCount) {resList.clear();resList.add(rootValue);maxCount = count;} else if (count == maxCount) {resList.add(rootValue);}pre = root;findMode1(root.right);
}

---

2- 题解

⭐ 二叉搜索树中的众数 ——题解思路

![class Solution {// 数据结构List<Integer> res = new ArrayList<>();](https://img-blog.csdnimg.cn/direct/66c7f6e9e0ac4b8fafecc31f1d480505.png)int count;int maxCount;TreeNode pre;public int[] findMode(TreeNode root) {count = 0;maxCount = 0;pre = new TreeNode();find(root);int[] resNums = new int[res.size()];for(int i = 0 ; i < resNums.length;i++){resNums[i] = res.get(i);}return resNums;}public void find(TreeNode root){if(root==null){return;}find(root.left);// 单层// 处理 count++ 逻辑int nowValue = root.val;if(pre==null || pre.val!=nowValue){count=1;}else{count+=1;}if(count>maxCount){res.clear();maxCount = count;res.add(nowValue);}else{res.add(nowValue);}pre = root;find(root.right);}
}

---

题目3: 二叉树的最近公共祖先

• 题目链接：236. 二叉树的最近公共祖先

---

1- 思路

递归三部曲

---

2- 题解

⭐ 二叉树的最近公共祖先 ——题解思路

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){return null;}else if(left!=null && right==null){return left;}else if(left==null && right!=null){return right;}else{return root;}}
}

这篇关于【随想录】Day21—第六章 二叉树part07的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---