leetCode如何計算二叉搜索樹的最小絕對差

一，二叉搜索樹的最小絕對差

1，問題簡述

給你一棵所有節(jié)點為非負(fù)值的二叉搜索樹，請你計算樹中任意兩節(jié)點的差的絕對值的最小值。

2，示例描述

示例：

輸入：

   1
    \
     3
    /
   2

輸出：
1

解釋：
最小絕對差為 1，其中 2 和 1 的差的絕對值為 1（或者 2 和 3）。

 

3，題解思路

基于中序遍歷獲取樹節(jié)點數(shù)據(jù)，進(jìn)行求解

4，題解程序

import java.util.ArrayList;
import java.util.List;

public class GetMinimumDifferenceTest {
    public static void main(String[] args) {
        TreeNode t1=new TreeNode(1);
        TreeNode t2=new TreeNode(3);
        TreeNode t3=new TreeNode(2);
        t1.right=t2;
        t2.left=t3;
        int minimumDifference = getMinimumDifference(t1);
        System.out.println("minimumDifference = " + minimumDifference);

    }

    public static  int getMinimumDifference(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return -1;
        }
        dfs(root, list);
        System.out.println("list = " + list);
        int[] toArray = list.stream().mapToInt(x -> x).toArray();
        int pre = toArray[0];
        int res = Integer.MAX_VALUE;
        for (int i = 1; i < toArray.length; i++) {
            res = Math.min(res, toArray[i] - pre);
            pre = toArray[i];
        }
        return res;
    }

    private static  void dfs(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            dfs(root.left, list);
        }
        list.add(root.val);
        if (root.right != null) {
            dfs(root.right, list);
        }
    }
}