leetcode 530. 二叉搜索树的最小绝对差
- 题目描述
- 解题思路
- 执行结果
题目描述
-
二叉搜索树的最小绝对差
给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。
示例 1：
输入：root = [4,2,6,1,3] 输出：1 示例 2：
输入：root = [1,0,48,null,null,12,49] 输出：1
提示：
树中节点的数目范围是 [2, 104] 0 <= Node.val <= 105
解题思路
法1
方法1 :中序遍历
-
二叉搜索树其实就类似于一个排序好的一组数据,左节点的数据大于根节点的数据大于右节点的数据,我们对其进行中序遍历就可以得到一组由小到大的递增数据,我们只需要判断这组数据中差值最小的就可以得到最小绝对差值
-
我们可以用递归的方法先左后中最后右的顺序遍历树从而实现二叉树的中序遍历
-
最后判断相邻两个数之间的差值,取最小的差值作为返回值
-
时间复杂度(O(n)) -
空间复杂度(O(1))
执行结果
法1
func getMinimumDifference(root *TreeNode) int {
prev, minDiff := -1, math.MaxInt32
traverse(root, &prev, &minDiff)
return minDiff
}
func traverse(node *TreeNode, prev *int, minDiff *int) {
if node == nil {
return
}
traverse(node.Left, prev, minDiff) //左节点
if *prev != -1 { //处理跟节点
if *minDiff > node.Val-*prev {
*minDiff = node.Val - *prev
}
}
*prev = node.Val
traverse(node.Right, prev, minDiff) //处理右节点
}
执行结果： 通过 显示详情 查看示例代码 添加备注
执行用时： 8 ms , 在所有 Go 提交中击败了 89.55% 的用户 内存消耗： 6.8 MB , 在所有 Go 提交中击败了 22.48% 的用户 通过测试用例： 189 / 189 炫耀一下:
法2
法3
本文由 mdnice 多平台发布