16. 二叉搜索树的最小绝对差（530）

一、题目内容 简单

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。

示例1：

输入：root = [4,2,6,1,3] 输出：1

示例2：

输入：root = [1,0,48,null,null,12,49] 输出：1

提示：

• 树中节点的数目范围是 [2, 104]
• 0 <= Node.val <= 105

  二、解题思路

  二叉搜索树实际上是有序的，那么相当于我们在有序数组中找出最小绝对差。
  只需要把相邻元素相减，找出其中最小绝对差就好了。
  那么我们第一步就应该是把二叉搜索树转成有序数组。

  二叉搜索树适合中序遍历。

三、具体代码

/**
 * @param {TreeNode} root
 * @return {number}
 */
var getMinimumDifference = function (root) {
  const nums = []
  const traversal = (node) => {
    if (!node) return
    traversal(node.left)
    nums.push(node.val)
    traversal(node.right)
  }
  traversal(root)
  let result = Infinity
  for (let i = 1, len = nums.length; i < len; i++) {
    result = Math.min(Math.abs(nums[i] - nums[i - 1]), result)
  }
  return result
};

四、其他解法

迭代法

/**
 * @param {TreeNode} root
 * @return {number}
 */
var getMinimumDifference = function (root) {
  const stack = []
  let result = Infinity
  let pre = null, cur = root
  while (cur || stack.length) {
    if (cur) {
      stack.push(cur)
      cur = cur.left
    } else {
      cur = stack.pop()
      if (pre) {
        result = Math.min(Math.abs(cur.val - pre.val), result)
      }
      pre = cur
      cur = cur.right
    }
  }
  return result
};