LeetCode530二叉搜索树的最小绝对差(未完待续)
程序员文章站
2022-04-24 20:44:41
...
题目
给你一棵所有节点为非负值的二叉搜索树,请你计算树中任意两节点的差的绝对值的最小值。
示例:
知识点
- 二叉树搜索树的特点
- 根结点的值大于左子树中任意一个结点的值,小于其右子树中任意一个结点的值,这一套规则适用于二叉搜索中的任意一个节点
- 二叉搜索树的中续遍历可以得到一个单调递增的序列
- 二叉树的中续遍历
- 请看另一篇博客:递归实现二叉树的遍历
解法一
算法
- 中序遍历二叉树,得到一个单调递增的列表;
- 任意两节点差的最小值,一定是对列表中相邻元素做差求得的。因此,求出列表中的相邻元素的差的最小值即可
class Solution {
List<Integer> nums=new ArrayList<>();
public int getMinimumDifference(TreeNode root) {
// 中序遍历得到数组
orderTraverse(root);
int min=Integer.MAX_VALUE;
for (int i = 0; i < nums.size()-1; i++) {
int difference=Math.abs(nums.get(i+1)-nums.get(i));
if (difference<min){
min=difference;
}
}
return min;
}
void orderTraverse(TreeNode root){
if(root==null){
return;
}
orderTraverse(root.left);
nums.add(root.val);
orderTraverse(root.right);
}
}
解法二
算法
- 中序遍历二叉树,使用一个pre指针指向
上一篇: 秀野堂html5入门视频教程的资源推荐
下一篇: 如何操作JS遍历多维数组