MinimumDistanceBetweenBSTNodes [source code]

public class MinimumDistanceBetweenBSTNodes {
static
/******************************************************************************/
class Solution {
    Integer min_dist;
    Integer prev;

    public int minDiffInBST(TreeNode root) {
        min_dist = null;
        prev = null;
        dfs (root);
        return min_dist;
    }

    void dfs (TreeNode node) {
        if (node == null)
            return;
        dfs (node.left);
        if (prev != null) {
            int dist = node.val - prev;
            if (min_dist == null || dist < min_dist)
                min_dist = dist;
        }
        prev = node.val;
        dfs (node.right);
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        MinimumDistanceBetweenBSTNodes.Solution tester = new MinimumDistanceBetweenBSTNodes.Solution();
    }
}

比较简单的一个题目, contest里面做的, 只要记住InOrder的traversal其实就跟一个sorted array没有差别, 然后你找最小的gap就行了;

速度是4ms (NA);

editorial

Approach #1: Write to Array [Accepted]

Intuition and Algorithm

Write all the values to an array, then sort it. The minimum distance must occur between two adjacent values in the sorted list.

这个思路就是没有利用BST的性质;

class Solution {  
    List<Integer> vals;  
    public int minDiffInBST(TreeNode root) {  
        vals = new ArrayList();  
        dfs(root);  
        Collections.sort(vals);  

        int ans = Integer.MAX_VALUE;  
        for (int i = 0; i < vals.size() - 1; ++i)  
            ans = Math.min(ans, vals.get(i+1) - vals.get(i));  

        return ans;  
    }  

    public void dfs(TreeNode node) {  
        if (node == null) return;  
        vals.add(node.val);  
        dfs(node.left);  
        dfs(node.right);  
    }  
}

一个小的要点, 就是想到用list来collect; 这个以前可能想不到是因为不知道list也是可以sort的;

Approach #2: In-Order Traversal [Accepted]

Intuition and Algorithm

In a binary search tree, an in-order traversal outputs the values of the tree in order. By remembering the previous value in this order, we could iterate over each possible difference, keeping the smallest one.

class Solution {  
    Integer prev, ans;  
    public int minDiffInBST(TreeNode root) {  
        prev = null;  
        ans = Integer.MAX_VALUE;  
        dfs(root);  
        return ans;  
    }  

    public void dfs(TreeNode node) {  
        if (node == null) return;  
        dfs(node.left);  
        if (prev != null)  
            ans = Math.min(ans, node.val - prev);  
        prev = node.val;  
        dfs(node.right);  
    }  
}

https://leetcode.com/problems/minimum-distance-between-bst-nodes/discuss/114834/Inorder-Traverse-O(N)-time-and-O(1)-space-C++JavaPython

class Solution {  
    Integer res = Integer.MAX_VALUE, pre = null;  
    public int minDiffInBST(TreeNode root) {  
        if (root.left != null) minDiffInBST(root.left);  
        if (pre != null) res = Math.min(res, root.val - pre);  
        pre = root.val;  
        if (root.right != null) minDiffInBST(root.right);  
        return res;  
    }  
}

就这么个题, 没了;

Problem Description

Given a Binary Search Tree (BST) with the root node root, return the minimum difference between the values of any two different nodes in the tree.

Example :

Input: root = [4,2,6,1,3,null,null]  
Output: 1  
Explanation:  
Note that root is a TreeNode object, not an array.  

The given tree [4,2,6,1,3,null,null] is represented by the following diagram:  

          4  
        /   \  
      2      6  
     / \      
    1   3    

while the minimum difference in this tree is 1, it occurs between node 1 and node 2, also between node 3 and node 2.

Note:

1. The size of the BST will be between 2 and 100.
2. The BST is always valid, each node's value is an integer, and each node's value is different.

Difficulty:Easy
Total Accepted:2.9K
Total Submissions:6K
Contributor:awice