leetcode530-二叉搜索树的最小绝对差

原题

给定一个所有节点为非负值的二叉搜索树,求树中任意两节点的差的绝对值的最小值。

示例:

输入:

   1
    \
     3
    /
  2

输出:
1
解释:
最小绝对差为1,其中 2 和 1 的差的绝对值为 1(或者 2 和 3)。

注意: 树中至少有2个节点。

解法

思想

中序遍历,计算两个相邻节点之间值的差的绝对值,比较出最小值。

代码

class Solution {
    int min = Integer.MAX_VALUE;
    int last = -1;
    public int getMinimumDifference(TreeNode root) {
        traverse(root);
        return min;
    }
    public void traverse(TreeNode root){
        if(root == null){
            return;
        }
        traverse(root.left);
        if(last!=-1) min = Math.min(min,root.val-last);
        last = root.val;
        traverse(root.right);
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode530-%e4%ba%8c%e5%8f%89%e6%90%9c%e7%b4%a2%e6%a0%91%e7%9a%84%e6%9c%80%e5%b0%8f%e7%bb%9d%e5%af%b9%e5%b7%ae/

发表评论

电子邮件地址不会被公开。