AlgoPressAppearance
0530-二叉搜索树的最小绝对差
https://leetcode.cn/problems/minimum-absolute-difference-in-bst
给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。 差值是一个正数，其数值等于两值之差的绝对值。
示例 1： 
输入：root = [4,2,6,1,3]
输出：1
示例 2： 
输入：root = [1,0,48,null,null,12,49]
输出：1
提示：
- 树中节点的数目范围是 [2, 104]
- 0 <= Node.val <= 105
注意：本题与 783 https://leetcode.cn/problems/minimum-distance-between-bst-nodes/ 相同
思路【分析错误】
二叉搜索树，左子树小于右子树，最小差值只能存在与 Math.Abs(根-左) 和 Math.Abs(根-右) 上 根据二叉搜索树的特性，上层和下层的值肯定会大于这个值。
递归并缓存最小值
下面的测试用例会错误，输出 123 实际应该为 9 = 236 - 227
出错的原因是：开始的假设就错误，最小差值有可能存在左子树的最右节点和根节点之间。 本题应该使用的思路就是 中序排列
236
/ \
104 701
\ \
227 911
参考代码
csharp
public class Solution {
int minValue = int.MaxValue;
private void dfs(TreeNode node){
if(node == null){
return ;
}
if(node.left != null){
minValue = Math.Min(minValue,Math.Abs(node.left.val - node.val));
}
if(node.right != null){
minValue = Math.Min(minValue,Math.Abs(node.right.val - node.val));
}
}
public int GetMinimumDifference(TreeNode root) {
dfs(node);
return minValue;
}
}
思路2：递归求值
我们应该求出左子树的最大值和右子树的最小值然后和主节点计算并求值更新当前的最小值。 而不是之和子节点去进行计算
csharp
public class Solution {
public int GetMinimumDifference(TreeNode root) {
int minValue = int.MaxValue;
if(root != null){
if(root.left != null){
TreeNode leftMost = root.left;
while(leftMost.right != null){
leftMost = leftMost.right;
}
minValue = Math.Min(minValue,Math.Abs(leftMost.val - root.val));
}
if(root.right != null){
TreeNode rightMost = root.right;
while(rightMost.left != null){
rightMost = rightMost.left;
}
minValue = Math.Min(minValue,Math.Abs(rightMost.val - root.val));
}
//计算子节点
minValue = Math.Min(minValue,GetMinimumDifference(root.left));
minValue = Math.Min(minValue,GetMinimumDifference(root.right));
}
return minValue;
}
}
思路3：【官方：中序遍历】 重要
中序遍历，二叉树就是升序数组，其最小值应该就是相邻像个树的最小值差 注意中序遍历，需要使用 pre 表示前一个节点
csharp
public class Solution {
int minValue = int.MaxValue;
int pre = -1;
private void dfs(TreeNode root){
if(root == null){
return;
}
dfs(root.left);
if(pre == -1){
//第一个节点先不计算差值
pre = root.val;
}
else{
minValue = Math.Min(minValue,Math.Abs(root.val - pre));
pre = root.val;
}
dfs(root.right);
}
public int GetMinimumDifference(TreeNode root) {
dfs(root);
return minValue;
}
}