Posted on 2023-06-14 14:57
Uriel 阅读(34)
评论(0) 编辑 收藏 引用 所属分类:
搜索 、
数据结构 、
闲来无事重切Leet Code
求二叉搜索树中元素值之差最小是多少,DFS中序遍历的同时记录当前节点和上一次访问的节点值之差即可
1 #530
2 #Runtime: 44 ms (Beats 43.16%)
3 #Memory: 17.3 MB (Beats 71.85%)
4
5 # Definition for a binary tree node.
6 # class TreeNode(object):
7 # def __init__(self, val=0, left=None, right=None):
8 # self.val = val
9 # self.left = left
10 # self.right = right
11 class Solution(object):
12 def getMinimumDifference(self, root):
13 """
14 :type root: TreeNode
15 :rtype: int
16 """
17 self.ans = 100000
18 self.pre_val = None
19
20 def DFS(node):
21 if not node:
22 return
23 DFS(node.left)
24 if self.pre_val is not None:
25 self.ans = min(self.ans, node.val - self.pre_val)
26 self.pre_val = node.val
27 DFS(node.right)
28
29 DFS(root)
30 return self.ans