Welcome to Subscribe On Youtube
783. Minimum Distance Between BST Nodes
Description
Given the root
of a Binary Search Tree (BST), return the minimum 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, 100]
. 0 <= Node.val <= 105
Note: This question is the same as 530: https://leetcode.com/problems/minimum-absolute-difference-in-bst/
Solutions
-
/** * 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 int ans; private int prev; private int inf = Integer.MAX_VALUE; public int minDiffInBST(TreeNode root) { ans = inf; prev = inf; dfs(root); return ans; } private void dfs(TreeNode root) { if (root == null) { return; } dfs(root.left); ans = Math.min(ans, Math.abs(root.val - prev)); prev = root.val; dfs(root.right); } }
-
/** * 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: const int inf = INT_MAX; int ans; int prev; int minDiffInBST(TreeNode* root) { ans = inf, prev = inf; dfs(root); return ans; } void dfs(TreeNode* root) { if (!root) return; dfs(root->left); ans = min(ans, abs(prev - root->val)); prev = root->val; dfs(root->right); } };
-
# 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: Optional[TreeNode]) -> int: def dfs(root): if root is None: return dfs(root.left) nonlocal ans, prev ans = min(ans, abs(prev - root.val)) prev = root.val dfs(root.right) ans = prev = inf dfs(root) return ans
-
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func minDiffInBST(root *TreeNode) int { inf := 0x3f3f3f3f ans, prev := inf, inf var dfs func(*TreeNode) dfs = func(root *TreeNode) { if root == nil { return } dfs(root.Left) ans = min(ans, abs(prev-root.Val)) prev = root.Val dfs(root.Right) } dfs(root) return ans } func abs(x int) int { if x < 0 { return -x } return x }
-
var minDiffInBST = function (root) { let ans = Number.MAX_SAFE_INTEGER, prev = Number.MAX_SAFE_INTEGER; const dfs = root => { if (!root) { return; } dfs(root.left); ans = Math.min(ans, Math.abs(root.val - prev)); prev = root.val; dfs(root.right); }; dfs(root); return ans; };