二叉搜索树最小差值

[编程题]二叉搜索树最小差值

热度指数：1125 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一棵二叉搜索树，请你返回树中任意两节点之差的最小值。

数据范围：二叉树节点数满足 $2 \le n \le 10^5 \$ ，二叉树的节点值满足 $0 \le val \le 10^9 \$ ，保证每个节点的值都不同

示例1

输入

{2,1,3,#,#,#,4}

输出

示例2

输入

{3,1,5,#,#,#,9}

输出

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

a_fighter_named_rudy

发表于 2022-10-25 18:30:19

解答：看到二叉搜索树，就思考二叉搜索树的中序遍历为有序数组是否有用，哎因为这题是求最小差值，所以能用该技巧，首先通过O(n)将二叉搜索树中序遍历结果存储到res数组中，然后因为res数组是上升的所以最小值只可能是i减i-1，所以for循环遍历结果数组得到最小值然后输出。总时间复杂度为O(n),空间复展开全文

訾尤

发表于 2022-04-27 15:57:30

public class Solution { public int minDifference (TreeNode root) { List<Integer> list = new ArrayList<>(); // 首先进行中序遍历展开全文

君无颜

发表于 2022-03-25 22:45:08

方法一（更容易理解）先中序遍历取出二叉搜索树的升序数组（二叉搜索树都是左小右大）然后遍历相减，比大小 c++实现 class Solution { public: vector<int> t; void mid(TreeNode* root){ i 展开全文

BlueProtocol

发表于 2022-10-08 13:45:02

public class MinDifference { private List<Integer> list = new ArrayList<Integer>(); public&n 展开全文

姐姐的遮阳伞

发表于 2022-04-06 21:18:44

import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int v 展开全文

extern

发表于 2024-02-05 13:44:51

/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) { 展开全文

extern

发表于 2024-02-05 13:51:04

package main import ( "math" . "nc_tools" ) /* * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode 展开全文