给定一棵二叉搜索树，请你返回树中任意两节点之差的最小值。
数据范围：二叉树节点数满足 
，二叉树的节点值满足 
，保证每个节点的值都不同
[编程题]二叉搜索树最小差值
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
vector<int> vec;
//中序遍历 左--中--右 得到的就是 中减去左 右减去中
void traversal(TreeNode*root){
if(root ==nullptr)return ;
traversal(root->left);
vec.push_back(root->val);
traversal(root->right);
}
int minDifference(TreeNode* root) {
// write code here
vec.clear();
traversal(root);
int res =INT_MAX;
for(int i=1;i<vec.size();i++){
res =min(res,vec[i]-vec[i-1]);
}
return res;
}
};
发表于 2022-04-13 20:05:54
回复(0)
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param root TreeNode类
# @return int整型
#
class Solution:
def minDifference(self , root: TreeNode) -> int:
# write code here
# 123456789
res = float("inf")
def f(root):
nonlocal res
if not root:
return
f(root.left)
if root.left:
res = min(res,root.val - root.left.val)
f(root.right)
if root.right:
res = min(res,root.right.val - root.val)
f(root)
return res
发表于 2025-06-15 12:17:39
回复(0)
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
int MIN(int a, int b) {
return a < b? a:b;
}
void dfs(struct TreeNode* root, int* arr, int *size){
if(root == NULL)
return ;
dfs(root->left, arr, size);
arr[(*size)++] = root->val;
dfs(root->right, arr, size);
}
int minDifference(struct TreeNode* root) {
// write code here
if(root == NULL)
return 0;
int size = 0;
int *res = (int*)calloc(pow(10, 5), sizeof(int));
dfs(root, res, &size);
int min_val = res[1] - res[0];
for(int i = 1; i < size; i++)
min_val = MIN(min_val, res[i] - res[i-1]);
return min_val;
}
发表于 2025-05-14 15:11:49
回复(0)
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param root TreeNode类
# @return int整型
#
class Solution:
def minDifference(self, root: TreeNode) -> int:
# write code here
order_list = []
def in_order(root):
nonlocal order_list
if not root:
return
in_order(root.left)
order_list.append(root.val)
in_order(root.right)
in_order(root)
diff = float("inf")
#删除了最左下角的节点，为啥?
#没删除，只是怕越界罢了，看循环体内的东西
#所以作者的思路确实就是跟另一个值比较
#这个值也不一定是相邻节点的
#比如
'''
1
2 3
5 10
深度算法的结果是2153 10 ，其中10和5并不相邻
那我大胆猜测，这个算法对这个例子是错误的
算法得到的结果是-2，但是实际上是1（考虑1和2）
'''
#而且也无法保证是绝对值，所以这里面缺失了关键的排序一步
order_list =sorted( order_list)
for i in range(1, len(order_list)):
diff = min(diff, order_list[i] - order_list[i - 1])
return diff
发表于 2024-07-17 17:55:29
回复(0)
遍历节点值，放在list中，遍历list查找出list差值最小的数据
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
int minNum = Integer.MAX_VALUE;
public int minDifference (TreeNode root) {
// write code here
List<Integer> lsit = new ArrayList<>();
mins(root,lsit);
for(int i=1;i<lsit.size();i++){
minNum = Math.min(Math.abs(lsit.get(i) - lsit.get(i-1)), minNum);
}
return minNum;
}
public void mins(TreeNode root, List<Integer> lsit) {
if (root == null) {
return;
}
lsit.add(root.val);
mins(root.left, lsit);
mins(root.right, lsit);
}
}
发表于 2023-11-28 16:08:18
回复(0)
- 对于二叉搜索树中任意节点，都有左子树节点的值 < 根节点的值 < 右子树节点的值。
- 二叉搜索树的中序遍历序列就是所有节点非降序排列的结果，而任意两个节点之差的最小值一定诞生于两个相邻节点之间。
- 因此，中序遍历并比较维护相邻两个节点之差的最小值即可。
class Solution {
public:
/**
* 二叉搜索树中任意节点，都有左子树节点的值 < 根节点的值 < 右子树节点的值
* 二叉搜索树的中序遍历序列就是所有节点非降序排列的结果，而任意节点的最小值
* 一定诞生于两个相邻节点之间。因此，中序遍历并比较维护相邻两个节点之差的最小值
* 即可。
* @param root TreeNode类
* @return int整型
*/
int minDifference(TreeNode* root) {
stack<TreeNode*> s;
int pre = -1000000000;
int curr = 1000000000;
int res = curr - pre;
while (!s.empty() || root) {
while (root) {
s.push(root);
root = root->left;
}
root = s.top();
s.pop();
// 计算中序遍历序列，相邻两个节点值的差
curr = root->val;
res = min(res, curr - pre);
pre = curr;
// 继续中序遍历
root = root->right;
}
return res;
}
};
发表于 2023-05-13 23:44:35
回复(0)
class Solution:
def minDifference(self , root: TreeNode) -> int:
# write code here
l = []
def inOrder(root):
if not root:
return
inOrder(root.left)
l.append(root.val)
inOrder(root.right)
inOrder(root)
ans = float('inf')
for i in range(1, len(l)):
ans = min(ans, l[i] - l[i-1])
return ans
发表于 2023-04-27 16:30:17
回复(0)
package main
//import "fmt"
import . "nc_tools"
/*
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
func minDifference( root *TreeNode ) int {
arr:=[]int{}
var order func(*TreeNode)
order=func(root *TreeNode){
if root==nil{
return
}
order(root.Left)
arr=append(arr,root.Val)
order(root.Right)
}
order(root)
ans:=arr[1]-arr[0]
for i:=1;i<len(arr)-1;i++{
tmp:=arr[i+1]-arr[i]
if tmp<ans{
ans=tmp
}
}
return ans
}
发表于 2023-03-09 08:30:01
回复(0)
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
int preorder(struct TreeNode* root, int* arr) {
static int count = 0;
if (NULL != root) {
arr[count++] = root->val;
preorder(root->left, arr);
preorder(root->right, arr);
}
return count;
}
int cnp(const void* e1,const void *e2){
return *(int*)e1-*(int*)e2;
}
int minDifference(struct TreeNode* root ) {
// write code here
int* arr=(int *)malloc(sizeof(int)*100000);
int count=preorder(root, arr);
qsort(arr,count,sizeof(int),cnp);
int ans=1000000000;
for(int i=1;i<count;i++){
if(ans>(arr[i]-arr[i-1]))
ans=arr[i]-arr[i-1];
}
return ans;
}
发表于 2023-01-10 16:35:29
回复(0)
思路也是中序遍历 但是超时了。
class Solution:
def inorderTravseral(self,root):if not root:
return []
return self.inorderTravseral(root.left) + [root.val] + self.inorderTravseral(root.right)
def minDifference(self , root: TreeNode) -> int:
re = self.inorderTravseral(root)
ans = float('inf')
for i in range(len(re)-2):
ans = min(ans, re[i+1] - re[i])
return ans
发表于 2022-07-02 20:29:59
回复(1)
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
int minDifference(TreeNode* root) {
// write code here
//用中序遍历得到最小值
help(root);
return minn;
}
void help(TreeNode* root)
{
if(!root)
{
return;
}
help(root->left);
minn=min(minn,abs(cur-root->val));
cur=root->val;
help(root->right);
}
private:
int cur=-999999;
int minn=999999;
};
发表于 2022-07-01 10:15:56
回复(0)
# -*- coding: utf-8 -*- class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class BT(object): def __init__(self): self.root = None def levelOrderToBT(self, nums): n = len(nums) if n > 0: self.root = TreeNode(nums[0]) queue, idx = [self.root], 1 while queue and idx < n: node = queue.pop(0) node.left = TreeNode(nums[idx]) if nums[idx] != None else None if node.left: queue.append(node.left) node.right = TreeNode(nums[idx + 1]) \ if idx + 1 < n and nums[idx + 1] != None else None if node.right: queue.append(node.right) idx += 2 return self.root @staticmethod def levelOrder(root): if not root: return [] queue, res = [root], [] while queue: node = queue.pop(0) if node: res.append(node.val) queue.append(node.left) queue.append(node.right) else: res.append(None) while res and res[-1] == None: res.pop() return res # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param root TreeNode类 # @return int整型 # class Solution: """ 题目： https://www.nowcoder.com/practice/f8ac976b49bd450887b9281f315186c7?tpId=196&tqId=40504&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title= 算法： 中序遍历二叉树，使用self.pre记录当前节点的前驱节点的val，不断更新差值diff与self.pre 复杂度： 时间复杂度：O(N)，N为节点数 空间复杂度：O(H), H为树的高度 """ def minDifference(self, root): # write code here def inOrder(root): if root: inOrder(root.left) if self.pre == -1: self.pre = root.val else: self.diff = min(self.diff, abs(root.val - self.pre)) self.pre = root.val inOrder(root.right) self.diff, self.pre = 10 ** 9, -1 inOrder(root) return self.diff if __name__ == "__main__": sol = Solution() nums = [2, 1, 3, None, None, None, 4] # nums = [3, 1, 5, None, None, None, 9] # nums = [9, 4, 16, 1, 7, 11, 19] bt = BT() bt1 = bt.levelOrderToBT(nums) # print BT.levelOrder(bt1) res = sol.minDifference(bt1) print res
发表于 2022-06-23 15:48:17
回复(0)
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
public int minDifference(TreeNode root) {
// write code here
if (root == null) {
return -1;
}
return getMin(root);
}
private int getMin(TreeNode root) {
if (root.left != null && root.right != null) {
return Math.min(Math.min(root.val - root.left.val, root.right.val - root.val),
Math.min(getMin(root.right), getMin(root.left)));
} else if (root.left != null) {
return Math.min(root.val - root.left.val, getMin(root.left));
} else if (root.right != null) {
return Math.min(root.right.val - root.val, getMin(root.right));
} else {
return Integer.MAX_VALUE;
}
}
}
发表于 2022-03-27 21:47:20
回复(0)
问题信息
难度：
13条回答
11收藏
6603浏览
通过挑战的用户
查看代码-
2022-09-16 09:43:12
-
2022-09-14 00:54:25
-
2022-09-10 20:53:32
-
2022-09-07 22:19:30
-
2022-09-07 09:50:53
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
