一、LeetCode 530 二叉搜索树的最小绝对值
题目链接：530.二叉搜索树的最小绝对值
https://leetcode.cn/problems/minimum-absolute-difference-in-bst/
思路一：利用搜索二叉树的中序遍历结果为有序数组的性质，将遍历结果保存到数组中，再找最小绝对值。
class Solution {
List<Integer> list = new LinkedList<>();
public int getMinimumDifference(TreeNode root) {
//二叉搜索树的中序遍历结果是一个有序数组
midgo(root);
int ans = Integer.MAX_VALUE;
for(int i = 1; i < list.size(); i++){
int temp = list.get(i) - list.get(i-1);
if( temp < ans){
ans = temp;
}
}
return ans;
}
public void midgo(TreeNode root){
if(root == null){
return;
}
midgo(root.left);
list.add(root.val);
midgo(root.right);
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/思路二：利用pre节点记录上个遍历到的节点数值，直接完成递归遍历和计算。
class Solution {
int result = Integer.MAX_VALUE;
TreeNode pre = null;
public int getMinimumDifference(TreeNode root) {
travel(root);
return result;
}
public void travel(TreeNode root){
if(root == null){
return;
}
travel(root.left);
//前一个节点不为空，比较差值与已保存的最小绝对值
if(pre != null){
result = Math.min(result,root.val-pre.val);
}
//记录前一个节点
pre = root;
travel(root.right);
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/二、LeetCode 501 二叉搜索树中的众数
题目链接：501.二叉搜索树中的众数https://leetcode.cn/problems/find-mode-in-binary-search-tree/
思路：利用二叉搜索树中序遍历为有序数组的性质，设置pre记录上一个节点，对众数进行计数及结果更新。
//二叉搜索树特性：中序遍历结果为有序数组
class Solution {
List<Integer> list;
int maxCount;
int count;
TreeNode pre;
public int[] findMode(TreeNode root) {
list = new ArrayList<>();
maxCount = 0;
count = 0;
pre = null;
travel(root);
int n = list.size();
int[] ans = new int[n];
for(int i = 0; i < n; i++){
ans[i] = list.get(i);
}
return ans;
}
public void travel(TreeNode root){
if(root == null){
return;
}
travel(root.left);
//利用中序遍历特性计数
if(pre == null || root.val != pre.val){
count = 1;
}else{
count++;
}
//更新结果及maxCount
if(count > maxCount){
maxCount = count;
//最大值改变，清空结果
list.clear();
list.add(root.val);
}else if(count == maxCount){
//最大值未变，添加结果
list.add(root.val);
}
pre = root;
travel(root.right);
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/三、LeetCode 236 二叉树的最近公共祖先
题目链接：236.二叉树的最近公共祖先https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/明日待续......
