LeetCode 530. 二叉搜索树的最小绝对差 JAVA

墨蓝 2022-12-14 03:38 147阅读 0赞

给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。

示例：
    
    输入：
    
       1
        \
         3
        /
       2
    
    输出：
    1
    
    解释：
    最小绝对差为 1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：因为树为二叉搜索树，所以中序遍历可以得到排序的数组，而两个数最小绝对差必然存在两个相邻的数之间。所以有  
1、中序遍历二叉搜索树  
2、保存前一个结点的值，利用当前结点值-前一个结点值得到两者的绝对差  
3、将得到的绝对差和现保存的最小绝对差比较，若得到的绝对差较小，这现保存的最小绝对差替换为当前结点值-前一个结点值得到两者的绝对差

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        int pre;
        int ans;
        public int getMinimumDifference(TreeNode root) {
        
            pre=-1;
            ans=Integer.MAX_VALUE;
            search(root);
            return ans;
        }
        public void search(TreeNode root)
        {
        
            if(root==null) return;
            search(root.left);
            if(pre==-1) pre=root.val;
            else
            {
        
                ans=Math.min(root.val-pre,ans);
                pre=root.val;
            }
            search(root.right);
        }
    }