沈阳地区精神文明建设网站网络推广基础

学习目标：

• 530.二叉搜索树的最小绝对差
• 501.二叉搜索树中的众数
• 236. 二叉树的最近公共祖先

---

学习内容：

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

题目链接&&文章讲解
给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

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

class Solution {//前一个节点值TreeNode pre;//结果值 初始化为整数最大值int result = Integer.MAX_VALUE;public int getMinimumDifference(TreeNode root) {if(root==null)return 0;traversal(root);return result;}public void traversal(TreeNode node){//终止条件：node == nullif(node == null) return;//左traversal(node.left);//中if(pre != null &&node.val - pre.val < result) {result =  node.val - pre.val;}pre = node;//右traversal(node.right);}
}

---

501.二叉搜索树中的众数

题目链接&&文章讲解
给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

结点左子树中所含节点的值 小于等于 当前节点的值
结点右子树中所含节点的值 大于等于 当前节点的值
左子树和右子树都是二叉搜索树

//普通二叉树
class Solution {public int[] findMode(TreeNode root) {Map<Integer,Integer> map = new HashMap<>();List<Integer> list = new ArrayList<>();if (root == null) return list.stream().mapToInt(Integer::intValue).toArray();// 获得频率 Maptraveral(root, map);List<Map.Entry<Integer, Integer>> mapList = map.entrySet().stream().sorted((c1, c2) -> c2.getValue().compareTo(c1.getValue())).collect(Collectors.toList());list.add(mapList.get(0).getKey());// 把频率最高的加入 listfor (int i = 1; i < mapList.size(); i++) {if (mapList.get(i).getValue() == mapList.get(i - 1).getValue()) {list.add(mapList.get(i).getKey());} else {break;}}return list.stream().mapToInt(Integer::intValue).toArray();}void traveral(TreeNode node, Map<Integer, Integer> map){if(node == null) return;map.put(node.val, map.getOrDefault(node.val, 0) + 1);traveral(node.left, map);traveral(node.right, map);}
}//二叉搜索树
class Solution {ArrayList<Integer> resList = new ArrayList<>();;int maxCount = 0;int count = 0;TreeNode pre = null;public int[] findMode(TreeNode root) {traversal(root);int[] res = new int[resList.size()];for (int i = 0; i < resList.size(); i++) {res[i] = resList.get(i);}return res;}public void traversal(TreeNode node){if(node == null) return;//左traversal(node.left);//中if(pre == null) count = 1;else if(pre.val == node.val) count++;else count = 1;pre = node;if(count == maxCount) resList.add(node.val);if(count > maxCount) {resList.clear();resList.add(node.val);maxCount = count;}//右traversal(node.right);}
}

---

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

题目链接&&文章讲解

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

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {//终止条件if(root == null) return null;if(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 root;else if(left == null && right != null) return right;else if(left != null && right == null) return left;else return null;}
}

---