leetcode 530. 二叉搜索树的最小绝对差
题目描述
给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。
示例
输入：root = [4,2,6,1,3]
输出：1
题目链接
https://leetcode.cn/problems/minimum-absolute-difference-in-bst
解题思路
二叉搜索树的中序遍历就是从小到大排序的有序数组。那么只要在遍历过程中查找当前节点和上一节点的差值就好了。
class Solution {
private TreeNode prev = null;
private int res = Integer.MAX_VALUE;
public int getMinimumDifference(TreeNode root) {
travelTree(root);
return res;
}
// 中序遍历，在遍历中找最小值
public void travelTree(TreeNode root) {
if (root == null) return;
travelTree(root.left);
if (prev != null) {
res = Math.min(res, root.val - prev.val));
}
prev = root;
travelTree(root.right);
}
}
自己写的思路，有点屎山。本质还是找中序遍历的相邻点的差值
// 14m20s
class Solution {
public int getMinimumDifference(TreeNode root) {
if (root == null) return Integer.MAX_VALUE;
// 根节点和左子树最右节点差，根节点和右子树最左节点差
int subLeft = Integer.MAX_VALUE, subRight = Integer.MAX_VALUE;
if (root.left != null) subLeft = root.val - getLeftMax(root.left).val;
if (root.right != null) subRight = getRightMin(root.right).val - root.val;
subLeft = Math.min(subLeft, getMinimumDifference(root.left));
subRight = Math.min(subRight, getMinimumDifference(root.right));
return Math.min(subLeft, subRight);
}
public TreeNode getLeftMax(TreeNode root) {
TreeNode node = root;
while (node.right != null) {
node = node.right;
}
return node;
}
public TreeNode getRightMin(TreeNode root) {
TreeNode node = root;
while (node.left != null) {
node = node.left;
}
return node;
}
}
leetcode 501. 二叉搜索树中的众数
题目描述
给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
如果树中有不止一个众数，可以按 任意顺序 返回。
假定 BST 满足如下定义：
- 结点左子树中所含节点的值 小于等于 当前节点的值
- 结点右子树中所含节点的值 大于等于 当前节点的值
- 左子树和右子树都是二叉搜索树
示例
输入：root = [1,null,2,2]
输出：[2]
题目链接
https://leetcode.cn/problems/find-mode-in-binary-search-tree
解题思路
二叉搜索树性质，中序遍历是有序数组。那么只需要在此基础上进行统计 count
- 如果
root.val == prev.val，则count++ - 如果
root.val != prev.vla，则count = 1 - 同时，在此之前判断
count > maxCount，如果为真，则将已存的众数数组清空。添加当前节点。
class Solution {
int count;
int maxCount = 0;
TreeNode prev = null;
ArrayList<Integer> list = new ArrayList<>();
public int[] findMode(TreeNode root) {
travelTree(root);
int[] res = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
res[i] = list.get(i);
}
return res;
}
public void travelTree(TreeNode root) {
if (root == null) return;
travelTree(root.left);
if (prev == null || root.val != prev.val) {
count = 1;
} else {
count++;
}
if (count > maxCount) {
list.clear();
maxCount = count;
list.add(root.val);
} else if (count == maxCount){
list.add(root.val);
}
prev = root;
travelTree(root.right);
}
}
leetcode 236. 二叉树的最近公共祖先
题目描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
题目链接
https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree
解题思路
从上往下找，会存在以下情况
- 既不在左子树，也不在右子树。
- 在左右子树某一边。
- 左右子树各有一个。
采用递归遍历。函数 lowestCommonAncestor(root, p, q) 表示在以 root 为根的子树中寻找 p、q 的最近公共祖先：
- 若
root为 null，返回 null； - 若
root等于 p 或 q，返回 root； - 递归左右子树获取结果 left、right；
- 若左右都非空，说明 p、q 分别在两侧 → 当前节点即 LCA；
- 若只有一边非空，返回该非空节点；→都在同一边，那么非空的就是要找的公共祖先
- 若两边都为空，返回 null。
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 找到p,q节点
if (root == null || root == p || root == q) return root;
// 遍历左子树
TreeNode left = lowestCommonAncestor(root.left, p, q);
// 遍历右子树
TreeNode right = lowestCommonAncestor(root.right, p, q);
// 左右子树都没找到节点p, q
if (left == null && right == null) {
return null;
} else if (left == null && right != null) {
// 左子树没找到，右子树找到
return right;
} else if (left != null && right == null) {
// 右子树没找到，左子树找到
return left;
} else {
return root;
}
}
}
评论