目录
- 前言
- 题目
- 1.二叉搜索树中序遍历特性介绍（并且使用一个指针始终指向前一个）
- 全局变量
- 2. 本题思路分析：（中序遍历）
- 3. 算法实现
- 4. 算法坑点
前言
我在刷卡哥的“代码随想录”，自己的总结笔记均会放在“算法刷题-代码随想录”该专栏下。
代码随想录此题链接
题目
1.二叉搜索树中序遍历特性介绍（并且使用一个指针始终指向前一个）
- 二叉搜索树中序遍历是所有节点为递增顺序。
- 用一个TreeNode对象充当指向上一个遍历的节点的指针，
- 然后从遍历到第2个节点开始比较当前和上一个节点的差值与最小值的大小。
全局变量
- min是最小的值
int min = Integer.MAX_VALUE;//初始化为int的最大值
- TreeNode pre;上一个节点
2. 本题思路分析：（中序遍历）
此题可以使用递归遍历，
三部曲：
- 第一步确定参数和返回值
参数：当前节点
返回值：boolean值 - 第二步截止递归的条件
当前节点为null，则返回Integer.MAX_VALUE； - 第三步单层递归逻辑
中序遍历，先递归左孩子，不用考虑返回值的接收；
在处理中间节点，判断pre节点不为空（说明遍历的非第1个节点），则比较min和root节点和pre节点的差值，并且更新min。
将当前的节点赋值给pre。
再递归右孩子。
3. 算法实现
class Solution {
int min = Integer.MAX_VALUE;
TreeNode pre;
public int getMinimumDifference(TreeNode root) {
if(root == null){
return Integer.MAX_VALUE;
}
getMinimumDifference(root.left);
if(pre != null){
min = Math.min(min,root.val - pre.val);//二叉搜索树中序遍历节点逐渐递增
}
pre = root;
getMinimumDifference(root.right);
return min;
}
}
4. 算法坑点
暂无
