【Leetcode_总结】 783. 二叉搜索树结点最小距离 - python

Q：

给定一个二叉搜索树的根结点 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的差值。

链接：https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/description/

思路：对二叉搜索树进行中序遍历得到有序数组，然后遍历数组，取得最小差值

代码：

# 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):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root == None:
            return 0
        else:
            res = []
            self.middle_digui(root, res)
        if len(res) == 1:
            return res[0]
        min_ = res[1]-res[0]
        for i in range(2,len(res)):
            if res[i]-res[i-1] < min_:
                min_ = res[i]-res[i-1]
        return min_

    def middle_digui(self,root,res):
        if root == None:
            return
        self.middle_digui(root.left,res)
        res.append(root.val)
        self.middle_digui(root.right,res)