leetcode_530. 二叉搜索树的最小绝对差
【摘要】 目录
一、题目内容
二、解题思路
三、代码
一、题目内容
给你一棵所有节点为非负值的二叉搜索树,请你计算树中任意两节点的差的绝对值的最小值。
示例:
输入:
1 \ 3 / 2
输出: 1...
目录
一、题目内容
给你一棵所有节点为非负值的二叉搜索树,请你计算树中任意两节点的差的绝对值的最小值。
示例:
输入:
1
\
3
/
2输出:
1
解释:
最小绝对差为 1,其中 2 和 1 的差的绝对值为 1(或者 2 和 3)。
提示:
树中至少有 2 个节点。
本题与 783 https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/ 相同
二、解题思路
中序遍历BST得到递增序列,考虑相邻二值之差即可。
三、代码
-
# Definition for a binary tree node.
-
class TreeNode:
-
def __init__(self, x):
-
self.val = x
-
self.left = None
-
self.right = None
-
-
class Solution:
-
def getMinimumDifference(self, root: TreeNode) -> int:
-
inorder_list = []
-
def dfs(root):
-
if not root:
-
return
-
dfs(root.left)
-
inorder_list.append(root.val)
-
dfs(root.right)
-
dfs(root)
-
return min(inorder_list[i + 1] - inorder_list[i] for i in range(len(inorder_list) - 1))
-
-
-
if __name__ == '__main__':
-
a = TreeNode(1)
-
a.right = TreeNode(3)
-
a.right.left = TreeNode(2)
-
-
s = Solution()
-
ans = s.getMinimumDifference(a)
-
print(ans)
文章来源: nickhuang1996.blog.csdn.net,作者:悲恋花丶无心之人,版权归原作者所有,如需转载,请联系作者。
原文链接:nickhuang1996.blog.csdn.net/article/details/109025860
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)