783. 二叉搜索树节点最小距离

题目

方法一 转数组

题目给出的数据是放在二叉搜索树中。二叉搜索树的中序遍历的结果是从小到大排列的。

1. 用中序遍历二叉搜索树，得到从小到大排好序的数组
2. 比较排序好的素组两两间的差值

class Solution:def minDiffInBST(self, root: TreeNode) -> int:def in_order(root):if not root:returnstack = []r = []while root or stack:while root:# print(root.val)# 先序遍历stack.append(root)root = root.leftroot = stack.pop()r.append(root.val)# print(root.val)# 中序if root.right:root = root.rightelse:root = Nonereturn rr = in_order(root)l = len(r)res = float('inf')for i in range(1,l):if r[i+1]-r[i]<res:res = r[i+1]-r[i]return res

方法二 指向前一个元素的指针（暂时没弄出来）

参考

class Solution:def minDiffInBST(self, root: TreeNode) -> int:self.pre=float('-inf')self.res=float('inf')def dfs(root):if not root:returndfs(root.left)self.res=min(self.res,root.val-self.pre)self.pre=root.valdfs(root.right)dfs(root)return self.res

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！