[算法练习] Leetcode 783 二叉搜索树节点最小距离

题目

给定一个二叉搜索树的根结点 root, 返回树中任意两节点的差的最小值。
示例:
输入: root = [4,2,6,1,3,null,null] 输出: 1 解释: 注意: root 是树结点对象 (TreeNode object)，而不是数组。
给定的树 [4,2,6,1,3,null,null] 可表示为下图:

      4
    /   \
  2      6
 / \    
1   3  

最小的差值是 1, 它是节点 1 和节点 2 的差值, 也是节点 3 和节点 2 的差值。

注意:
二叉树的大小范围在 2 到 100。
二叉树总是有效的，每个节点的值都是整数，且不重复。

思路

因为是二叉搜索树(BST), BST的一个特点是中序遍历出的值是从小到大的, 所以可以输出一个排序后的列表, 再计算相邻之间每个值的差值

代码实现

   private List<Integer> list = new ArrayList();

    @Test
    public void test() {
        // 构造二叉搜索树(BST)
        Node rootNode = new Node(4);
        Node twoNode = new Node(2);
        Node oneNode = new Node(1);
        Node threeNode = new Node(3);
        Node sixNode = new Node(6);

        rootNode.left = twoNode;
        rootNode.right = sixNode;

        twoNode.left = oneNode;
        twoNode.right = threeNode;

        visit(rootNode);

        System.out.println(list);

        int min = Integer.MAX_VALUE;
        for (int index = 0; index < list.size() - 1; index++) {
            min = Math.min(min, (list.get(index + 1) - list.get(index)));
        }

        System.out.println("min: " + min);
    }

    // 中序遍历(从小到大)
    public void visit(Node node) {
        if (node == null) {
            return;
        }

        visit(node.left);  // 先访问左子树

        list.add(node.value);

        visit(node.right); // 再访问右子树
    }