本文主要是介绍leetcode-783. 二叉搜索树结点最小距离，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目
给定一个二叉搜索树的根结点 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的差值。
注意：
二叉树的大小范围在 2 到 100。
二叉树总是有效的，每个节点的值都是整数，且不重复。
解题思路
无脑版：按中序遍历把二叉树的结点保存好，然后从前向后遍历，找最小差值。时间复杂度是o(n)，空间复杂度o(n)
改进版：一次中序遍历，用prev保存前一个结点的值即可。
成绩
时间>91.13%
空间>32.43%
代码
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution(object):def minDiffInBST(self, root):""":type root: TreeNode:rtype: int"""min_diff = root.valprev_val = Nonestack = [(0, root)]while stack:stat, p = stack.pop()if stat == 0:if p.right:stack.append((0, p.right))stack.append((1, p))if p.left:stack.append((0, p.left))else:if not prev_val:prev_val = p.valcontinuemin_diff = min(min_diff, p.val - prev_val)prev_val = p.valreturn min_diff
注意事项
重写了下发现还是有很多小细节的
- 比如不应该用
root.val来初始化min_diff，因为可能root节点的值是0，但有右子树，此时最小的数字应该是右子树的leftest node和root.val之间的差值 - 再有一个，不应该用
not来判断prev_val，同理如果prev_val=0，会导致错误地进入条件，改为prev_val != None比较好
这篇关于leetcode-783. 二叉搜索树结点最小距离的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
