Description
Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.
Example 1:
Input: root = [4,2,6,1,3]
Output: 1
Example 2:
Input: root = [1,0,48,null,null,12,49]
Output: 1
Constraints:
- The number of nodes in the tree is in the range
[2, 104].
0 <= Node.val <= 105
Note: This question is the same as 783: https://leetcode.com/problems/minimum-distance-between-bst-nodes/
Solutions
Solution 1: Inorder Traversal
The problem requires us to find the minimum difference between the values of any two nodes. Since the inorder traversal of a binary search tree is an increasing sequence, we only need to find the minimum difference between the values of two adjacent nodes in the inorder traversal.
We can use a recursive method to implement the inorder traversal. During the process, we use a variable pre to save the value of the previous node. This way, we can calculate the minimum difference between the values of two adjacent nodes during the traversal.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary search tree.
PythonJavaC++GoTypeScriptRustJavaScript
# 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 getMinimumDifference(self, root: Optional[TreeNode]) -> int:
def dfs(root: Optional[TreeNode]):
if root is None:
return
dfs(root.left)
nonlocal pre, ans
ans = min(ans, root.val - pre)
pre = root.val
dfs(root.right)
pre = -inf
ans = inf
dfs(root)
return ans(code-box)
/**
* 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;
* }
* }
*/
class Solution {
private final int inf = 1 << 30;
private int ans = inf;
private int pre = -inf;
public int getMinimumDifference(TreeNode root) {
dfs(root);
return ans;
}
private void dfs(TreeNode root) {
if (root == null) {
return;
}
dfs(root.left);
ans = Math.min(ans, root.val - pre);
pre = root.val;
dfs(root.right);
}
}(code-box)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int getMinimumDifference(TreeNode* root) {
const int inf = 1 << 30;
int ans = inf, pre = -inf;
auto dfs = [&](this auto&& dfs, TreeNode* root) -> void {
if (!root) {
return;
}
dfs(root->left);
ans = min(ans, root->val - pre);
pre = root->val;
dfs(root->right);
};
dfs(root);
return ans;
}
};(code-box)
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func getMinimumDifference(root *TreeNode) int {
const inf int = 1 << 30
ans, pre := inf, -inf
var dfs func(*TreeNode)
dfs = func(root *TreeNode) {
if root == nil {
return
}
dfs(root.Left)
ans = min(ans, root.Val-pre)
pre = root.Val
dfs(root.Right)
}
dfs(root)
return ans
}(code-box)
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function getMinimumDifference(root: TreeNode | null): number {
let [ans, pre] = [Infinity, -Infinity];
const dfs = (root: TreeNode | null) => {
if (!root) {
return;
}
dfs(root.left);
ans = Math.min(ans, root.val - pre);
pre = root.val;
dfs(root.right);
};
dfs(root);
return ans;
}(code-box)
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
pub fn get_minimum_difference(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
const inf: i32 = 1 << 30;
let mut ans = inf;
let mut pre = -inf;
fn dfs(node: Option<Rc<RefCell<TreeNode>>>, ans: &mut i32, pre: &mut i32) {
if let Some(n) = node {
let n = n.borrow();
dfs(n.left.clone(), ans, pre);
*ans = (*ans).min(n.val - *pre);
*pre = n.val;
dfs(n.right.clone(), ans, pre);
}
}
dfs(root, &mut ans, &mut pre);
ans
}
}(code-box)
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var getMinimumDifference = function (root) {
let [ans, pre] = [Infinity, -Infinity];
const dfs = root => {
if (!root) {
return;
}
dfs(root.left);
ans = Math.min(ans, root.val - pre);
pre = root.val;
dfs(root.right);
};
dfs(root);
return ans;
};(code-box)
