算法训练营第二十一天(二叉树part7)
530.二叉搜索树的最小绝对差
力扣题目链接(opens new window)
题目
给你一棵所有节点为非负值的二叉搜索树,请你计算树中任意两节点的差的绝对值的最小值。
示例:
提示:树中至少有 2 个节点。
解答
方法一
利用搜索树的特性,使用中序放入数组中,数组一定是递增序列,最小的一定是相邻的两个的差值
//递归法
class Solution {
public int getMinimumDifference(TreeNode root) {
List<Integer> results = new ArrayList<>();//递增序列
travel(root,results);
int min = Integer.MAX_VALUE;
for (int i = 0; i < results.size() - 1; i++) {
min = Math.min(min,Math.abs(results.get(i) - results.get(i + 1)));
}
return min;
}
private void travel(TreeNode cur,List<Integer> results){
if (cur == null)
return;
travel(cur.left,results);
results.add(cur.val);
travel(cur.right,results);
}
}
//迭代法
class Solution {
public int getMinimumDifference(TreeNode root) {
List<Integer> results = new ArrayList<>();//递增序列
Stack<TreeNode> stack = new Stack<>();
while (root != null || !stack.isEmpty()){
while (root != null){
stack.push(root);
root = root.left;
}
//此时栈顶是最左侧的子树的根节点,每一次循环如果没有右子树就会进行一次回溯
TreeNode cur = stack.pop();
results.add(cur.val);
root = cur.right;
}
int min = Integer.MAX_VALUE;
for (int i = 0; i < results.size() - 1; i++) {
min = Math.min(min,Math.abs(results.get(i) - results.get(i + 1)));
}
return min;
}
}
方法二:双指针(推荐)
class Solution {
int result = Integer.MAX_VALUE;
TreeNode pre;
public int getMinimumDifference(TreeNode root) {
travel(root);
return result;
}
private void travel(TreeNode cur){
if (cur == null)
return;
travel(cur.left);
if (pre != null)
result = Math.min(result,Math.abs(cur.val - pre.val));
pre = cur;
travel(cur.right);
}
}
travel(cur.left);
在最后一次跳出循环时,此时cur指向最左侧的1,而pre指向null- 接下来进行
中
,pre指向这一轮的cur,即1 - 然后
travel(cur.right);
,同样为空 - cur=1这一轮结束,然后进行回溯,此时这一轮的cur指向4,因为跳出了上一层递归,而pre指向上一轮的cur即1
501.二叉搜索树中的众数
力扣题目链接(opens new window)
题目
给定一个有相同值的二叉搜索树(BST),找出 BST 中的所有众数(出现频率最高的元素)。
假定 BST 有如下定义:
- 结点左子树中所含结点的值小于等于当前结点的值
- 结点右子树中所含结点的值大于等于当前结点的值
- 左子树和右子树都是二叉搜索树
例如:
给定 BST [1,null,2,2],
返回[2].
提示:如果众数超过1个,不需考虑输出顺序
进阶:你可以不使用额外的空间吗?(假设由递归产生的隐式调用栈的开销不被计算在内)
解答
常规做法(没使用搜索树的特性,不推荐)
class Solution {
public int[] findMode(TreeNode root) {
Map<Integer,Integer> map = new HashMap<>();
travel(root,map);
List<Map.Entry<Integer, Integer>> sortedEntries = new ArrayList<>(map.entrySet());
sortedEntries.sort((entry1, entry2) -> entry2.getValue().compareTo(entry1.getValue()));//降序
List<Integer> result = new ArrayList<>();
int count = sortedEntries.get(0).getValue();
for (Map.Entry<Integer, Integer> sortedEntry : sortedEntries) {
if (sortedEntry.getValue() == count)
result.add(sortedEntry.getKey());
else
break;
}
// 转换为 Integer[]
Integer[] arr = result.toArray(new Integer[0]);
// 再转换为 int[]
int[] intArr = Arrays.stream(arr).mapToInt(Integer::intValue).toArray();
return intArr;
}
private void travel(TreeNode root,Map<Integer,Integer> map){
if (root == null)
return;
travel(root.left,map);
map.put(root.val,map.getOrDefault(root.val,0) + 1);
travel(root.right,map);
}
}
使用搜索树特性(双指针)
不使用额外空间,还是使用递归,但是由于是搜索树,所以如果使用中序只要是相同的数一定会相邻,那么如果达到最大的count就放入,如果比最大的count还大,就清空列表,重新放入
必须是双指针,不然一个指向左子树,另一个找不到根
class Solution {
ArrayList<Integer> results;
int maxCount;
int count;
TreeNode pre;
public int[] findMode(TreeNode root) {
results = new ArrayList<>();
maxCount = 0;
count = 0;
pre = null;
travel(root);
int[] result = new int[results.size()];
for (int i = 0; i < results.size(); i++) {
result[i] = results.get(i);
}
return result;
}
private void travel(TreeNode cur){
if (cur == null)
return;
travel(cur.left);
if (pre != null && pre.val == cur.val)
count++;
else
count = 1;
pre = cur;
if (count == maxCount)
results.add(cur.val);
if (count > maxCount){
results.clear();
maxCount = count;
results.add(pre.val);
}
travel(cur.right);
}
}
236.二叉树的最近公共祖先
力扣题目链接(opens new window)
题目
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
例如,给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
示例 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。因为根据定义最近公共祖先节点可以为节点本身。
说明:
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉树中。
解答
后序
情况1:p与q分别在左右子树
情况2:一个在左右子树,一个在根
if (root == p || root == q)
return root;//满足第二种情况
//该代码解决了情况二
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
return travel(root, p, q);
}
private TreeNode travel(TreeNode root, TreeNode p, TreeNode q){
if (root == null)
return null;
if (root == p || root == q)
return root;//满足第二种情况
TreeNode left = travel(root.left,p,q);
TreeNode right = travel(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 //left == null && right == null
return null;
}
}
eNode right = travel(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 //left == null && right == null
return null;
}
}