The problem requires us to find the minimum difference between the values of any two nodes. Since the inorder traversal of a binary search tree is an increasing sequence, we only need to find the minimum difference between the values of two adjacent nodes in the inorder traversal.
We can use a recursive method to implement the inorder traversal. During the process, we use a variable $\textit{pre}$ to save the value of the previous node. This way, we can calculate the minimum difference between the values of two adjacent nodes during the traversal.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of nodes in the binary search tree.
1 2 3 4 5 6 7 8 9101112131415161718192021
# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclassSolution:defgetMinimumDifference(self,root:Optional[TreeNode])->int:defdfs(root:Optional[TreeNode]):ifrootisNone:returndfs(root.left)nonlocalpre,ansans=min(ans,root.val-pre)pre=root.valdfs(root.right)pre=-infans=infdfs(root)returnans
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcgetMinimumDifference(root*TreeNode)int{constinfint=1<<30ans,pre:=inf,-infvardfsfunc(*TreeNode)dfs=func(root*TreeNode){ifroot==nil{return}dfs(root.Left)ans=min(ans,root.Val-pre)pre=root.Valdfs(root.Right)}dfs(root)returnans}