Minimum Absolute Difference in BST

Tags: Binary Search Tree, Easy

Question

Problem Statement

Given a binary search tree with non-negative values, find the minimum
absolute difference
between values of any two nodes.

Example:

  1. **Input:**
  3.    1
  4.     \
  5.      3
  6.     /
  7.    2
  9. **Output:**
  10. 1
  12. **Explanation:**
  13. 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.

题解

题意为找任意两个节点间绝对值差的最小值，根据二叉搜索树的特性，中序遍历即得有序数组，找出相邻两数的最小差值即为解。

Java - Recursive

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. public class Solution {
  11.     private int min = Integer.MAX_VALUE;
  12.     private TreeNode prev = null;
  14.     public int getMinimumDifference(TreeNode root) {
  15.         if (root == null) return min;
  17.         getMinimumDifference(root.left);
  18.         if (prev != null) {
  19.             min = Math.min(min, root.val - prev.val);
  20.         }
  21.         prev = root;
  22.         getMinimumDifference(root.right);
  23.         return min;
  24.     }
  25. }

Java - Iterative

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. public class Solution {
  11.     public int getMinimumDifference(TreeNode root) {
  12.         int min = Integer.MAX_VALUE;
  13.         TreeNode prev = null;
  14.         Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
  16.         while (root != null || (!stack.isEmpty())) {
  17.             if (root != null) {
  18.                 stack.push(root);
  19.                 root = root.left;
  20.             } else {
  21.                 root = stack.pop();
  22.                 if (prev != null) {
  23.                     min = Math.min(min, root.val - prev.val);
  24.                 }
  25.                 prev = root;
  26.                 root = root.right;
  27.             }
  28.         }
  30.         return min;
  31.     }
  32. }

源码分析

递归的解法中需要特别注意 min 和 prev 的设定，作为参数传入均不太妥当。由于二叉搜索树的特性，求得最小差值时无需判断绝对值。

复杂度分析

递归实现用了隐式栈，迭代实现用了显式栈，最坏情况下栈的大小均为节点总数，平均情况下为树的高度。故平均情况下空间复杂度为 O(\log n), 每个节点被访问一次，时间复杂度为 O(n).

Reference