0530-二叉搜索树的最小绝对差
2021/11/18 23:39:55
本文主要是介绍0530-二叉搜索树的最小绝对差,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
给你一个二叉搜索树的根节点 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
注意:本题与 783 https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/ 相同
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst
参考:
- https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst/solution/530-er-cha-sou-suo-shu-de-zui-xiao-jue-dui-chai-yo/
python
# 0530.二叉搜索树的最小绝对差 # 递归-中序-数组比较 class Solution: def getMinimumDifference(self, root: *TreeNode) -> int: res = [] r = float("inf") def buildaList(root): # 把二叉搜索树转换成有序数组 if not root: return None if root.left: buildaList(root.left) # 左 res.append(root.val) # 中 if root.right: buildaList(root.right) # 右 return res buildaList(root) for i in range(len(res) - 1): # 统计有序数组的最小差值 r = min(abs(res[i] - res[i + 1]), r) return r class Solution1: def getMinimumDifference(self, root: *TreeNode) -> int: result = 1<<63-1 pre = None def travel(node): nonlocal result, pre if not node: return travel(node.left) if pre != None: result = min(result, node.val-pre.val) pre = node # 记录前一个 travel(node.right) travel(root) return result class Solution2: def getMinimumDifference(self, root: TreeNode) -> int: stack = [] cur = root pre = None result = 1<<63-1 while cur or stack: if cur: # 遍历至最左左节点 stack.append(cur) cur = cur.left else: # 处理栈顶元素 cur = stack.pop() if pre: result = min(result, cur.val-pre.val) pre = cur cur = cur.right return result
golang
package binaryTree import "math" // 递归-中序-数组比较 func getMinimumDifference1(root *TreeNode) int { res := []int{} var travel func(node *TreeNode) travel = func(node *TreeNode) { if node == nil { return } travel(node.Left) res = append(res, node.Val) travel(node.Right) } travel(root) if len(res) < 2 { return 0 } Min := math.MaxInt64 for i:=1;i<len(res);i++ { temp := res[i] - res[i-1] if Min > temp { Min = temp } } return Min } // 递归-中序前驱节点-利用BST的性质 func getMinimumDifference2(root *TreeNode) int { result := math.MaxInt64 var pre *TreeNode var travel func(node *TreeNode) travel = func(node *TreeNode) { if node == nil { return } travel(node.Left) if pre != nil { temp := node.Val - pre.Val if result > temp { result = temp } } pre = node travel(node.Right) } travel(root) return result } // 迭代-中序遍历-有限变量处理 func getMinimumDifference3(root *TreeNode) int { stack := []*TreeNode{} cur := root var pre *TreeNode result := math.MaxInt64 for cur != nil || len(stack) > 0 { if cur != nil { stack = append(stack, cur) cur = cur.Left } else { cur = stack[len(stack)-1] stack = stack[:len(stack)-1] if pre != nil { temp := cur.Val - pre.Val if result > temp { result = temp } } pre = cur cur = cur.Right } } return result }
这篇关于0530-二叉搜索树的最小绝对差的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-06小米11i印度快充版ROM合集:极致体验,超越期待
- 2024-10-06【ROM下载】小米11i 5G 印度版系统, 疾速跃迁,定义新速度
- 2024-10-06【ROM下载】小米 11 青春活力版,青春无极限,活力全开
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求