问题描述
解法
分析
Python 实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
|
class : def getMinimumDifference(self, root): """ :type root: TreeNode :rtype: int """ def dfs(node): if node: dfs(node.left) self.ans = min(self.ans, node.val - self.prev) self.prev = node.val dfs(node.right) self.prev = float('-inf') self.ans = float('inf') dfs(root) return self.ans
|
Java 实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
|
* Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class { private int ans; private int prev; private void dfs(TreeNode node){ if(node != null){ dfs(node.left); int newDist = node.val - prev; ans = this.ans < newDist ? ans : newDist; prev = node.val; dfs(node.right); } } public int getMinimumDifference(TreeNode root) { ans = Integer.MAX_VALUE; prev = -9999; dfs(root); return ans; } }
|
时间复杂度
O(N).
空间复杂度
O(L).
链接
530. Minimum Absolute Difference in BST
530. 二叉搜索树的最小绝对差
(English version) Algorithm Notes: Leetcode#530 Minimum Absolute Difference in BST
近期评论