算法训练营（day21）
530. 二叉搜索树的最小绝对差
题目链接：https://leetcode.cn/problems/minimum-absolute-difference-in-bst/description/
给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。
解题思路
解题过程：中序遍历
思路一：递归
- 记录 上一个节点值， 记为
pre
- 通过中序遍历，取出 当前节点
root 和 pre 的差
- 返回差的最小值
思路二：迭代
详细代码
解法一：递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
class Solution {
TreeNode pre;
int result = Integer.MAX_VALUE;
public int getMinimumDifference(TreeNode root) {
if(root == null){
return 0;
}
DFS(root);
return result;
}
public void DFS(TreeNode node){
if(node == null){
return;
}
DFS(node.left);
if(pre != null){
result = Math.min(result, node.val - pre.val);
}
pre = node;
DFS(node.right);
}
}
|
解法二：迭代
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
class Solution {
TreeNode pre;
Stack<TreeNode> stack = new Stack<>();
int result = Integer.MAX_VALUE;
public int getMinimumDifference(TreeNode root) {
BFS(root);
return result;
}
public void BFS(TreeNode node){
if(node == null){
return;
}
while(node != null || !stack.isEmpty()){
if(node != null){
stack.push(node);
node = node.left;
}else {
node = stack.pop();
if(pre != null){
result = Math.min(result, node.val - pre.val);
}
pre = node;
node = node.right;
}
}
}
}
|
501. 二叉搜索树中的众数
题目链接：https://leetcode.cn/problems/find-mode-in-binary-search-tree/description/
给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
如果树中有不止一个众数，可以按 任意顺序 返回。
假定 BST 满足如下定义：
- 结点左子树中所含节点的值 小于等于 当前节点的值
- 结点右子树中所含节点的值 大于等于 当前节点的值
- 左子树和右子树都是二叉搜索树
解题思路
解题过程：中序遍历
解法一：中序遍历(递归)
- 通过中序遍历，取二叉搜索树的每一个值
- 当节点值第一次出现，定义
count 为1
- 如果不是第一次出现，则
count++
- 定义一个最大数量
maxCount
- 当
count > maxCount 时，要更新 最高频率众数 集合 result
- 当
count = maxCount 时，将当前节点值放入集合
- 遍历集合，返回数组格式
解法二：中序遍历思路的迭代
详细代码
解法一：中序遍历(递归)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
class Solution {
List<Integer> result = new ArrayList<>();
TreeNode pre;
int count = 0;
int maxCount = 0;
public int[] findMode(TreeNode root) {
findModebyInorder(root);
int[] res = new int[result.size()];
for(int i = 0; i < result.size(); i++){
res[i] = result.get(i);
}
return res;
}
public void findModebyInorder(TreeNode node){
if(node == null){
return;
}
findModebyInorder(node.left);
if(pre == null || node.val != pre.val){
count = 1;
}else{
count++;
}
if(count > maxCount){
result.clear();
result.add(node.val);
maxCount = count;
}else if(count == maxCount){
result.add(node.val);
}
pre = node;
findModebyInorder(node.right);
}
}
|
解法二：迭代
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
class Solution {
TreeNode pre;
Stack<TreeNode> stack = new Stack<>();
List<Integer> result = new ArrayList<>();
int maxCount = 0;
int count = 0;
public int[] findMode(TreeNode root) {
findModeByBFS(root);
return result.stream().mapToInt(Integer::intValue).toArray();
}
public void findModeByBFS(TreeNode node){
if(node == null){
return;
}
while(node != null || !stack.isEmpty()){
if(node != null){
stack.push(node);
node = node.left;
}else {
node = stack.pop();
if(pre == null || node.val != pre.val){
count = 1;
}else{
count++;
}
if(count > maxCount){
result.clear();
result.add(node.val);
maxCount = count;
}else if(count == maxCount){
result.add(node.val);
}
pre = node;
node = node.right;
}
}
}
}
|
236. 二叉树的最近公共祖先
题目链接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
解题思路
解题过程：
- 本题使用递归的方法求解
- 公共祖先有两种情况
- 左右节点的 根节点
- 指定节点本身就是公共节点
详细代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
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 root;
}
return left != null ? left : right;
}
}
|
