Python3、Java 实现「783. 二叉搜索树节点最小距离」
与你一起学算法
共 4844字，需浏览 10分钟
·
2021-04-14 20:37
783. 二叉搜索树节点最小距离
题目链接
https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/
也可以点击「阅读原文」直达题目链接。
题目描述
给你一个二叉搜索树的根节点 root，返回 树中任意两不同节点值之间的最小差值。
示例 1：
输入：root = [4, 2, 6, 1, 3]
输出：1
示例 2：
输入：root = [1, 0, 48, null, null, 12, 49]
输出：1
提示：
树中节点数目在范围 [2, 100]内
解题思路
这道题主要是考察二叉搜索树的性质，二叉搜索树的中序遍历得到的结果是升序排列的。要得到树中任意两个不同节点值之间的最小差值，那么只需要比较中序遍历得到的序列的相邻元素，求得最小值就可以了。
这道题看上去有点无从下手的感觉，但是碰到二叉搜索树，就一定要想到的中序遍历是有序的，这几乎是碰到二叉搜索树的必考点。
Python3 代码
# 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 = right
class Solution:
def minDiffInBST(self, root: TreeNode) -> int:
self.inorder_result = []
self.inorder(root)
ans = 10 ** 5 + 1
size = len(self.inorder_result)
for i in range(1, size):
ans = min(ans, self.inorder_result[i] - self.inorder_result[i - 1])
return ans
def inorder(self, root: TreeNode) -> int:
if root:
self.inorder(root.left)
self.inorder_result.append(root.val)
self.inorder(root.right)
Java 代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
import java.util.List;
import java.util.ArrayList;
class Solution {
private List<Integer> list;
public int minDiffInBST(TreeNode root) {
list = new ArrayList<>();
this.inorder(root);
int ans = 100001;
for (int i = 1; i < list.size(); ++i) {
ans = Math.min(ans, list.get(i) - list.get(i - 1));
}
return ans;
}
public void inorder(TreeNode root) {
if (root != null) {
this.inorder(root.left);
this.list.add(root.val);
this.inorder(root.right);
}
}
}
复杂度分析：
时间复杂度：
空间复杂度：
好了，今天的内容就到这里了。我最近在学习数据结构与算法的相关知识，也会在力扣进行每日一题的打卡。如果你最近在求职面试或者也在进行力扣进行每日一题的打卡的话，欢迎加入我们，后台回复「加群」即可。我一直坚信一个人走的更快，一群人走的更远。很多时候，只要坚持下去了，那么你就超越了很多人。
参考资料：
https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/solution/python3-java-shi-xian-783-er-cha-sou-suo-uika/
评论