Posted on 2023-06-14 14:57
Uriel 閱讀(50)
評論(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