AlgoViz Lab交互式算法学习Algorithms first
二叉搜索树的最小绝对差 · 交互式算法学习
找出 BST 任意两节点值的最小绝对差。
#530 · 二叉搜索树
二叉搜索树的最小绝对差
Minimum Absolute Difference in BST
root = [4,2,6,1,3]树 / 图3 个关键状态
步骤 1中序先访问 1。
prev=1推荐
中序遍历相邻比较
时间
O(n)空间 O(h)BST 中序天然升序，只需保存前一个值。
1function getMinimumDifference(root) {2 let prev = null,3 best = Infinity;4 5 function dfs(n) {6 if (!n) return;7 dfs(n.left);8 if (prev !== null) best = Math.min(best, n.val - prev);9 prev = n.val;10 dfs(n.right)11 }12 dfs(root);13 return best;14}多语言参考
来源 · CC BY-SA 4.0 ↗Java · C++ · Go
这是一组同题正确实现，独立于上方当前动画方法；不同语言可能采用另一种正确策略。
1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 * int val;5 * TreeNode left;6 * TreeNode right;7 * TreeNode() {}8 * TreeNode(int val) { this.val = val; }9 * TreeNode(int val, TreeNode left, TreeNode right) {10 * this.val = val;11 * this.left = left;12 * this.right = right;13 * }14 * }15 */16class Solution {17 private final int inf = 1 << 30;18 private int ans = inf;19 private int pre = -inf;20 21 public int getMinimumDifference(TreeNode root) {22 dfs(root);23 return ans;24 }25 26 private void dfs(TreeNode root) {27 if (root == null) {28 return;29 }30 dfs(root.left);31 ans = Math.min(ans, root.val - pre);32 pre = root.val;33 dfs(root.right);34 }35}交互式算法学习
从执行步骤真正理解 LeetCode 经典 150
本站整理 150 道高频算法面试题和 302 种解法。动画方法同步展示 JavaScript 与 Python；每题另提供 Java、C++ 与 Go 同题参考实现。
AlgoViz Lab
二叉搜索树的最小绝对差 · 解法对比
找出 BST 任意两节点值的最小绝对差。
- 测试用例
root = [4,2,6,1,3]- 题目分类
- 二叉搜索树
- 解法对比
- 2
收集排序后比较相邻
收集全部值排序，最小差只可能出现在相邻项。
- 时间
O(n log n)- 空间
O(n)
中序遍历相邻比较
BST 中序天然升序，只需保存前一个值。
- 时间
O(n)- 空间
O(h)