Lt530. 二叉搜索树的最小绝对差

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

给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。
示例：
输入：

1
   \
    3
   /
  2

输出：
1
解释：
最小绝对差为 1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。
提示：

• 树中至少有 2 个节点。
• 本题与 783 https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/ 相同

思路

数组做法

考点二叉搜索树的中序遍历是一个递增数组。得到遍历结果以后，再遍历判断当前值和上一值得绝对值大小，求出最小的差距两个值即可。

遍历时求出

相比于上一种方式不需要一个数组来储存中序遍历结果。

解答

数组做法

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var getMinimumDifference = function (root) {
  const res = [];
  const visit = (node) => {
    if (!node) return;
    visit(node.left);
    res.push(node.val);
    visit(node.right);
  };
  visit(root);
  if (res.length == 2) return Math.abs(res[0] - res[1]);
  let min = Math.abs(res[0] - res[1]);
  for (let i = 2; i < res.length; i++) {
    min = Math.min(min, Math.abs(res[i] - res[i - 1]));
  }
  return min;
};

遍历时求出

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var getMinimumDifference = function (root) {
  const res = [];
  let min = Number.MAX_SAFE_INTEGER;
  let preNode = null;
  const inorder = (node) => {
    if (!node) return;
    inorder(node.left);
    if (preNode) {
      min = Math.min(Math.abs(node.val - preNode.val), min);
    }
    preNode = node;
    inorder(node.right);
  };
  inorder(root);
  return min;
};