算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
今天和大家聊的问题叫做 二叉搜索树的最小绝对差,我们先来看题面:
https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst/
Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.
给你一个二叉搜索树的根节点 root ,返回 树中任意两不同节点值之间的最小差值 。差值是一个正数,其数值等于两值之差的绝对值。
思路:利用二叉搜索树-中序遍历递归
class Solution {
// 二叉搜索树的最小绝对差
int min_diff = Integer.MAX_VALUE;
int pre = -1;
public int getMinimumDifference(TreeNode root) {
// 中序遍历
if(root==null){
return min_diff;
}
// 左根右
getMinimumDifference(root.left);
if(pre!=-1){
min_diff = Math.min(Math.abs(root.val-pre),min_diff);
pre = root.val;
}else{
pre = root.val;
}
getMinimumDifference(root.right);
return min_diff;
}
}
好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。
上期推文: