代码随想录算法训练营day21 | 题目530、题目501、题目236、题目508、题目652
题目一描述
给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。
示例 1：
输入：root = [4,2,6,1,3]
输出：1
示例 2：
输入：root = [1,0,48,null,null,12,49]
输出：1
提示：
树中节点的数目范围是 [2, 10^4]
0 <= Node.val <= 10^5
解题思路
中序遍历，依旧暂存上一个结点，然后做对比。
代码实现
方法一：
class Solution {
int res = Integer.MAX_VALUE;
TreeNode pre; // 注意不要初始化，就是null了
public int getMinimumDifference(TreeNode root) {
if (root == null)
return 0;
dfs(root);
return res;
}
public void dfs(TreeNode root) {
if (root == null)
return;
dfs(root.left);
if (pre != null) {
res = Math.min(res, root.val - pre.val); // root必然大于pre
}
pre = root;
dfs(root.right);
}
}
题目二描述
给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即出现频率最高的元素）。
如果树中有不止一个众数，可以按 任意顺序 返回。
假定 BST 满足如下定义：
结点左子树中所含节点的值 小于等于 当前节点的值
结点右子树中所含节点的值 大于等于 当前节点的值
左子树和右子树都是二叉搜索树
示例 1：
输入：root = [1,null,2,2]
输出：[2]
示例 2：
输入：root = [0]
输出：[0]
提示：
树中节点的数目在范围 [1, 10^4] 内
-10^5 <= Node.val <= 10^5
解题思路
中序遍历，同步维护计数的状态，元素相同的次数变多时更新答案。
代码实现
方法一：
class Solution {
TreeNode pre;
List<Integer> res = new ArrayList<>();
int maxCount = 0;
int curCount = 0;
public int[] findMode(TreeNode root) {
dfs(root);
int[] ress = new int[res.size()];
for (int i = 0; i < ress.length; i++) {
ress[i] = res.get(i);
}
return ress;
}
private void dfs(TreeNode root) {
if (root == null)
return;
dfs(root.left);
if (pre != null) {
if (pre.val == root.val) {
curCount++;
} else {
curCount = 1;
}
} else {
curCount = 1;
}
if (curCount == maxCount) {
res.add(root.val);
}
if (curCount > maxCount) {
res.clear();
res.add(root.val);
maxCount = curCount;
}
pre = root;
dfs(root.right);
}
}
题目三描述
236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：
输入：root = [1,2], p = 1, q = 2
输出：1
提示：
树中节点数目在范围 [2, 105] 内。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。
解题思路
可以前序遍历，找到并记录到子结点的路径，然后找最后一个不一样的结点。
但是只要想找的结果同时需要左子树和右子树的信息，就用后序遍历比较好，比如说求高度，比如说判断是不是平衡二叉树，比如说跟子树相关的问题。
这样就可以从底部把信息带上来，最后汇总到跟结点并退出递归。
本题本质上是利用了返回值是不是空，来返回有没有找到解的一种手段。
本题的后序遍历是常考的问题，需要记下来这个最优解。
代码实现
方法一（效率很不好）：
class Solution {
List<TreeNode> path1;
List<TreeNode> path2;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
getPath(root, p, new ArrayList<>(), true);
getPath(root, q, new ArrayList<>(), false);
TreeNode res = root;
for (int i = 0; i < Math.min(path1.size(), path2.size()); i++) {
if (path1.get(i) == path2.get(i)) {
res = path1.get(i);
} else {
break;
}
}
return res;
}
private boolean getPath(TreeNode root, TreeNode target, List<TreeNode> path, boolean flag) {
if (root == null)
return false;
path.add(root);
if (root == target || getPath(root.left, target, path, flag) || getPath(root.right, target, path, flag)) {
if (flag == true) {
path1 = new ArrayList(path);
} else {
path2 = new ArrayList(path);
}
return true;
}
path.remove(path.size() - 1);
return false;
}
}
方法二：
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;
}
if (left != null && right != null) {
return root;
}
if (left != null) {
return left;
}
if (right != null) {
return right;
}
return root;
}
}
题目四描述
508. 出现次数最多的子树元素和
给你一个二叉树的根结点 root ，请返回出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。
一个结点的 「子树元素和」 定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。
示例 1：
输入: root = [5,2,-3]
输出: [2,-3,4]
示例 2：
输入: root = [5,2,-5]
输出: [2]
提示:
节点数在 [1, 10^4] 范围内
-10^5 <= Node.val <= 10^5
解题思路
类似于求众数，也是后序遍历比较好，从底部把子树的结果带上来。
代码实现
方法一：
class Solution {
List<Integer> resList = new ArrayList<>();
int maxCount = 0;
Map<Integer, Integer> map = new HashMap<>();
public int[] findFrequentTreeSum(TreeNode root) {
dfs(root);
int[] res = new int[resList.size()];
for (int i = 0; i < res.length; i++) {
res[i] = resList.get(i);
}
return res;
}
private int dfs(TreeNode root) {
if (root == null) {
return 0;
}
int left = dfs(root.left);
int right = dfs(root.right);
int sum = root.val + left + right;
int curCount = map.getOrDefault(sum, 0) + 1;
map.put(sum, curCount);
if (curCount > maxCount) {
maxCount++;
resList.clear();
resList.add(sum);
} else if (curCount == maxCount) {
resList.add(sum);
}
return sum;
}
}
题目五描述
给你一棵二叉树的根节点 root ，返回所有 重复的子树 。
对于同一类的重复子树，你只需要返回其中任意 一棵 的根结点即可。
如果两棵树具有 相同的结构 和 相同的结点值 ，则认为二者是 重复 的。
示例 1：
输入：root = [1,2,3,4,null,2,4,null,null,4]
输出：[[2,4],[4]]
示例 2：
输入：root = [2,1,1]
输出：[[1]]
示例 3：
输入：root = [2,2,2,3,null,3,null]
输出：[[2,3],[3]]
提示：
树中的结点数在 [1, 5000] 范围内。
-200 <= Node.val <= 200
解题思路
将树序列化为字符串，存入map比对出现次数。
注意序列化只能用前序或者后序。
整体而言，也是后序遍历，在后序里做字符串拼接。
代码实现
方法一：
class Solution {
List<TreeNode> res = new ArrayList<>();
Map<String, Integer> map = new HashMap<>();
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
dfs(root);
return new ArrayList(res);
}
private String dfs(TreeNode root) {
if (root == null) {
return "#,";
}
String left = dfs(root.left);
String right = dfs(root.right);
StringBuilder mid = new StringBuilder();
mid.append(root.val).append(",").append(left).append(right);
String midString = mid.toString();
if (map.getOrDefault(midString, 0) == 1) {
res.add(root);
}
map.put(midString, map.getOrDefault(midString, 0) + 1);
return midString;
}
}
技巧总结
map.getOrDefault()并不会创建新的键值对，只是在空的时候返回一个值，所以需要put去操作。
