给定一个二叉搜索树的根节点 root，返回树中任意两节点的差的最小值。

 

示例：

输入: root = [4,2,6,1,3,null,null]
输出: 1
解释:
注意，root是树节点对象(TreeNode object)，而不是数组。

给定的树 [4,2,6,1,3,null,null] 可表示为下图:

4
/ \
2 6
/ \
1 3

最小的差值是 1, 它是节点1和节点2的差值, 也是节点3和节点2的差值。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def minDiffInBST(self, root: TreeNode) -> int:
        def preorderTraversal(root):
            node, output = root, []
            while node:  
                if not node.left: 
                    output.append(node.val)
                    node = node.right 
                else: 
                    predecessor = node.left 

                    while predecessor.right and predecessor.right is not node: 
                        predecessor = predecessor.right 

                    if not predecessor.right:
                        output.append(node.val)
                        predecessor.right = node  
                        node = node.left  
                    else:
                        predecessor.right = None
                        node = node.right         

            return output
        nodes=preorderTraversal(root)
        nodes.sort(reverse=True)
        _min=float('inf')
        for i in range(len(nodes)-1):
            _min=min(_min,nodes[i]-nodes[i+1])
        return _min

 

 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def minDiffInBST(self, root: TreeNode) -> int:
        if not root:return
        pre=float('-inf')
        _min=float('inf')
        stack=[]
        cur=root
        while stack or cur:
            while cur:
                stack.append(cur)
                cur=cur.left
            cur=stack.pop()
            _min=min(_min,cur.val-pre)
            pre=cur.val
            cur=cur.right
        return _min