LeetCode : 783. Minimum Distance Between BST Nodes

[congr]

https://leetcode.com/problems/minimum-distance-between-bst-nodes/

[congr]

O(N^2), AC

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int min = Integer.MAX_VALUE;

    public int minDiffInBST(TreeNode root) {
        if (root == null) return 0;
        minDiff(root, root.val);

        minDiffInBST(root.left);
        minDiffInBST(root.right);
        return min;
    }

    void minDiff(TreeNode node, int val) {
        if (node == null) return;

        if (node.left != null) min = Math.min(min, Math.abs(node.left.val - val));
        if (node.right != null) min = Math.min(min, Math.abs(node.right.val - val));

        minDiff(node.left, val);
        minDiff(node.right, val);
    }
}

[congr]

O(N)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int min = Integer.MAX_VALUE;
    TreeNode last;

    public int minDiffInBST(TreeNode root) {
        if (root == null) return 0;

        last = null;
        inorder(root);

        return min;
    }

    void inorder(TreeNode node) {
        if (node == null) return;

        inorder(node.left);
        if (last != null) min = Math.min(min, node.val - last.val);
        last = node;
        inorder(node.right);
    }
}