530. Minimum Absolute Difference in BST

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.

思路1：

用一个list，存储全部的TreeNode。在list中，计算任意两个数之差的绝对值，求这个绝对值的最小值。 时间复杂度O(n2)。

思路2：

题目给的是BST树，可以利用BST树的性质：左子树中节点的最大值 < 根 < 右子树中节点的最小值
两个TreeNode之差的绝对值的最小值一定出现在 | 左 - 根 | 或 | 根 - 右 |之中。而非 | 右 - 左 |。
所以，只要从root，把树分成左子树和右子树，分别来计算就可以了。 这是第一个条件。

第二个条件， 根的值一定介于：左子树的最右节点 与 右子树的最左节点 之间。
举个例子，236介于227和240之间：

根据这个原则，可以分别写两个函数求左子树的最右节点，和右子树的最左节点。然后分别递归左子树和右子树。
不过这种方法有一个缺点，就是每次都需要求左子树的最右节点，和右子树的最左节点。

Java 代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int getMinimumDifference(TreeNode root) {
        int min = Integer.MAX_VALUE;
        if(root == null) return min;
        TreeNode leftChildMostRight = getLeftChildMostRight(root.left);
        TreeNode rightChildMostLeft = getRightChildMostLeft(root.right);
        if(leftChildMostRight != null) {
            min = Math.min(min, Math.abs(leftChildMostRight.val - root.val));
        }
        if(rightChildMostLeft != null) {
            min = Math.min(min, Math.abs(rightChildMostLeft.val - root.val));
        }
        int min1 = Math.min(min, getMinimumDifference(root.left));
        int min2 = Math.min(min, getMinimumDifference(root.right));
        return Math.min(min, Math.min(min1, min2));
    }

    // 左子树的最右节点
    public TreeNode getLeftChildMostRight(TreeNode root) {
        if(root == null) {
            return root; 
        }
        while(root.right != null) {
            root = root.right;
        }    
        return root;
    }

    // 右子树的最左节点
    public TreeNode getRightChildMostLeft(TreeNode root) {
        if(root == null) {
            return root; 
        }
        while(root.left != null) {
            root = root.left;
        }    
        return root;
    }

}