530. 二叉搜索树的最小绝对差（BST）

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

• 题目
• 解题思路
• 代码

题目

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

提示：

• 树中至少有 2 个节点。
• 本题与 783相同

解题思路

解法一：
该题第一种解法。是我自己想出来的垃圾解法， 就把所有的节点的值放入list，再遍历list，进行相减。定义一个min，每次相减的结果与min进行比较。不断更新min。

解法二：
因为是二叉搜索树，所以我们用中序遍历，这样二叉树的节点值是从小到达排列的。
我们只需要在每次进行中序遍历时，把当前值.val 与前一个元素的.val相减，并且更新min

代码

解法一：

class Solution {
    public int getMinimumDifference(TreeNode root) {
        List<Integer> list =new ArrayList<>();
        findAllRoot(list,root);//现在的list已经存有所有节点的值了
        int min=Integer.MAX_VALUE;
        for(int i=0;i<list.size();i++){ 
            for(int j=i+1;j<list.size();j++){ 
                int num=list.get(i)-list.get(j);
                    if(num<0){
                        num=(-1)*num;
                    }

                    if(num<min){
                        min=num;
                    }
            
                } 
        }
    return min;

    }
    public void findAllRoot(List<Integer> list,TreeNode root){//找到所有节点的值，并加入到list中 
    if(root==null){ 
        return ; 
        } 
        list.add(root.val); 
        findAllRoot(list,root.left);
         findAllRoot(list,root.right);
          }

}

解法二：

class Solution {

     TreeNode pre = null;
    int min = Integer.MAX_VALUE;//这俩变量要定义为成员变量，不然每次递归都会重置他们。

      public int getMinimumDifference(TreeNode root) {
        help(root);
        return min;
    }

    public void help(TreeNode root) {
        if (root == null) {
            return;
        }
        help(root.left);
        //中序遍历
        if (pre != null) {
            int cur = (root.val) - (pre.val);
            if (cur < 0) {
                cur = (-1) * cur;
            }
            if (cur < min) {
                min = cur;
            }
        }
        pre = root;
        help(root.right);

    }
}