Leetcode.530 二叉搜索树的最小绝对差

题目链接

Leetcode.530 二叉搜索树的最小绝对差 easy

题目描述

给你一个二叉搜索树的根节点 root，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

示例 1：

输入：root = [4,2,6,1,3]
输出：1

示例 2：

输入：root = [1,0,48,null,null,12,49]
输出：1

提示：

• 树中节点的数目范围是 [2,104][2, 10^4][2,104]
• 0<=Node.val<=1050 <= Node.val <= 10^50<=Node.val<=105

解法：中序遍历

因为给定的是一棵 二叉搜索树。 中序遍历 结点值是按 从小到大 排序的。

所以我们用 pre记录前一个结点，用 ans记录最小的绝对值差。

每次更新 ans=min{ans,root.val−pre.val}ans = min \\{ ans , root.val - pre.val \\}ans=min{ans,root.val−pre.val}。

时间复杂度： $O(n)$

C++代码：

class Solution {
public:int ans = 1e9;TreeNode * pre = nullptr;void dfs(TreeNode * root){if(root == nullptr) return;dfs(root->left);if(pre == nullptr) pre = root;else{ans = min(ans , root->val - pre->val);pre = root;}dfs(root->right);}int getMinimumDifference(TreeNode* root) {dfs(root);return ans;}
};