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

链接：530.二叉搜索树的最小绝对差
难度：Easy
标签：树、深度优先搜索、广度优先搜索、二叉搜索树、二叉树
简介：给定一个所有节点为非负值的二叉搜索树，求树中任意两节点的差的绝对值的最小值。

题解 1 - java

• 编辑时间：2020-02-23
• 执行用时：2ms
• 内存消耗：40.5MB
• 编程语言：java
• 解法介绍：中序遍历后判断数组前后值相减的最小值。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
	ArrayList<Integer> list = new ArrayList<Integer>();
    public int getMinimumDifference(TreeNode root) {
		inorder(root);
		int min = list.get(1)-list.get(0);
		for(int i =0,len=list.size()-1;i<len;i++)
			min=Math.min(list.get(i+1)-list.get(i), min);
		return min;
	}
	public void inorder(TreeNode node) {
		if (node.left != null) {
			inorder(node.left);
		}
		list.add(node.val);
		if (node.right != null) {
			inorder(node.right);
		}
	}
}

题解 2 - typescript

• 编辑时间：2020-10-12
• 执行用时：108ms
• 内存消耗：44.6MB
• 编程语言：typescript
• 解法介绍：中序遍历排序后进行判断。

function getMinimumDifference(root: TreeNode | null): number {
  if (root === null) return 2147483647;
  const queue: number[] = [];
  inorder(root);
  return queue.reduce(
    (total, cur, i, arr) => (i === 0 ? total : Math.min(total, Math.abs(cur - arr[i - 1]))),
    Infinity
  );
  function inorder(node: TreeNode | null): void {
    if (node === null) return;
    inorder(node.left);
    queue.push(node.val);
    inorder(node.right);
  }
}