刷题leetcode--530. Minimum Absolute Difference in BST

柔光的暖阳◎ 2021-10-09 03:50 486阅读 0赞

**530. Minimum Absolute Difference in BST![奋斗][struggle.gif]2018.1.11**

Given a binary search tree with non-negative values, find the minimum [absolute difference][] between values of any two nodes.

Example:

Input:
    
       1
        \
         3
        /
       2
    
    Output:
    1
    
    Explanation:
    The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).

Note: There are at least two nodes in this BST.

**题意**:找任意两点的差值的  最小值。（差的绝对值的最小值）

知识点：**二叉搜索树BST ，中序遍历**

** 二叉搜索树的中序遍历是有序数组**。二叉搜索树特点：任何节点的值都比它的左子节点的值要大，比右子节点的值要小。（上一篇博客）

相邻节点的差值和全局最小值相比，分组比较（左子结点-> root）（root->右子结点），参数里的pre是相对变化的。对左子树的递归来说，pre指左子结点，对右子树来说pre变成了原来的root。

普通树的遍历是前序遍历。写的递归的函数（root.left和root.right）放在逻辑处理的后面。这里是把root.left放在前面。root.right放在后面，对root的处理放中间，这种写法是中序遍历。

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    
    
    class Solution {
          Integer min = Integer.MAX_VALUE;
          Integer pre = null;
        
          public int getMinimumDifference(TreeNode root) {
          if(root == null)
              return min;
          //中序遍历方法  先找左子树      
          getMinimumDifference(root.left); 
          if(pre !=null){   // 对当前节点的操作
              min=Math.min(root.val - pre,min); //当前节点和左子树的差值与min比较
          }
          pre = root.val;  //把当前节点值变成pre，进行右边子树的递归
          getMinimumDifference(root.right);   //遍历右子树
          return min;
            
            
        }
    }

[struggle.gif]: /images/20211009/590dbca127734dea836ec81643325dfa.png
[absolute difference]: https://en.wikipedia.org/wiki/Absolute_difference