783.二叉搜索树节点最小距离

链接：783.二叉搜索树节点最小距离
难度：Easy
标签：树、深度优先搜索、广度优先搜索、二叉搜索树、二叉树
简介：给定一个二叉搜索树的根结点 root, 返回树中任意两节点的差的最小值。

题解 1 - java

• 编辑时间：2020-02-23
• 内存消耗：36.9MB
• 编程语言：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 minDiffInBST(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

• 编辑时间：2021-04-13
• 执行用时：88ms
• 内存消耗：39.8MB
• 编程语言：typescript
• 解法介绍：中序遍历。

function minDiffInBST(root: TreeNode | null): number {
  if (root === null) return 0;
  const arr: number[] = [];
  const inorder = (node: TreeNode | null) => {
    if (node === null) return;
    inorder(node.left);
    arr.push(node.val);
    inorder(node.right);
  };
  inorder(root);
  let min = Infinity;
  for (let i = 1, l = arr.length; i < l; i++) {
    min = Math.min(min, arr[i] - arr[i - 1]);
  }
  return min;
}