Dado un árbol de búsqueda binario de tamaño N > 1 , la tarea es encontrar la mínima diferencia absoluta entre dos Nodes cualesquiera.
Ejemplos:
Input:
5
/ \
3 7
/ \ / \
2 4 6 8
Output: 1
Difference between all the consecutive nodes if sorted is 1.
Thus, the answer is 1.
Input:
1
\
6
Output: 5
Enfoque: sabemos que el recorrido en orden de un árbol de búsqueda binario lo atraviesa en orden ordenado. Entonces, para cada Node, encontraremos su diferencia con el Node anterior en el recorrido en orden del árbol. Si esta diferencia es menor que la diferencia mínima anterior, actualizaremos la diferencia mínima anterior. Los siguientes son los pasos a seguir:
- Cree una variable ‘anterior’ para almacenar el puntero al Node anterior en un recorrido en orden.
- Cree una variable ‘ans’ para almacenar la diferencia mínima.
- Para cada Node en el recorrido en orden, compare su diferencia absoluta con el Node anterior y actualice la diferencia absoluta mínima encontrada hasta el momento.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Node of the binary tree
struct node {
int data;
node* left;
node* right;
node(int data)
{
this->data = data;
left = NULL;
right = NULL;
}
};
// Function for in-order traversal of the tree
void inorder(node* curr, node*& prev, int& ans)
{
// Base-case
if (curr == NULL)
return;
// Calling in-order on the left sub-tree
inorder(curr->left, prev, ans);
if (prev != NULL)
ans = min(curr->data - prev->data, ans);
prev = curr;
// Calling in-order on the right sub-tree
inorder(curr->right, prev, ans);
}
// Function to return the minimum
// difference between any two nodes
// of the given binary search tree
int minDiff(node* root)
{
// Pointer to previous node in the
// in-order traversal of the BST
node* prev = NULL;
// To store the final ans
int ans = INT_MAX;
// Call in-order for the BST
inorder(root, prev, ans);
// Returning the final answer
return ans;
}
// Driver code
int main()
{
node* root = new node(5);
root->left = new node(3);
root->right = new node(7);
root->left->left = new node(2);
root->left->right = new node(4);
root->right->left = new node(6);
root->right->right = new node(8);
cout << minDiff(root);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Node of the binary tree
static class node
{
int data;
node left;
node right;
node(int data)
{
this.data = data;
left = null;
right = null;
}
};
static node prev;
static int ans;
// Function for in-order traversal of the tree
static void inorder(node curr)
{
// Base-case
if (curr == null)
return;
// Calling in-order on the left sub-tree
inorder(curr.left);
if (prev != null)
ans = Math.min(curr.data -
prev.data, ans);
prev = curr;
// Calling in-order on the right sub-tree
inorder(curr.right);
}
// Function to return the minimum
// difference between any two nodes
// of the given binary search tree
static int minDiff(node root)
{
// Pointer to previous node in the
// in-order traversal of the BST
prev = null;
// To store the final ans
ans = Integer.MAX_VALUE;
// Call in-order for the BST
inorder(root);
// Returning the final answer
return ans;
}
// Driver code
public static void main(String[] args)
{
node root = new node(5);
root.left = new node(3);
root.right = new node(7);
root.left.left = new node(2);
root.left.right = new node(4);
root.right.left = new node(6);
root.right.right = new node(8);
System.out.println(minDiff(root));
}
}
// This code is contributed by 29AjayKumar
C#
// C# implementation of the approach
using System;
class GFG
{
// Node of the binary tree
public class node
{
public int data;
public node left;
public node right;
public node(int data)
{
this.data = data;
left = null;
right = null;
}
};
static node prev;
static int ans;
// Function for in-order traversal of the tree
static void inorder(node curr)
{
// Base-case
if (curr == null)
return;
// Calling in-order on the left sub-tree
inorder(curr.left);
if (prev != null)
ans = Math.Min(curr.data -
prev.data, ans);
prev = curr;
// Calling in-order on the right sub-tree
inorder(curr.right);
}
// Function to return the minimum
// difference between any two nodes
// of the given binary search tree
static int minDiff(node root)
{
// Pointer to previous node in the
// in-order traversal of the BST
prev = null;
// To store the final ans
ans = int.MaxValue;
// Call in-order for the BST
inorder(root);
// Returning the final answer
return ans;
}
// Driver code
public static void Main(String[] args)
{
node root = new node(5);
root.left = new node(3);
root.right = new node(7);
root.left.left = new node(2);
root.left.right = new node(4);
root.right.left = new node(6);
root.right.right = new node(8);
Console.WriteLine(minDiff(root));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript implementation of the approach
// Node of the binary tree
class node
{
constructor(data)
{
this.data = data;
this.left = null;
this.right = null;
}
};
var prev = null;
var ans =0;
// Function for in-order traversal of the tree
function inorder(curr)
{
// Base-case
if (curr == null)
return;
// Calling in-order on the left sub-tree
inorder(curr.left);
if (prev != null)
ans = Math.min(curr.data -
prev.data, ans);
prev = curr;
// Calling in-order on the right sub-tree
inorder(curr.right);
}
// Function to return the minimum
// difference between any two nodes
// of the given binary search tree
function minDiff(root)
{
// Pointer to previous node in the
// in-order traversal of the BST
prev = null;
// To store the final ans
ans = 10000000000;
// Call in-order for the BST
inorder(root);
// Returning the final answer
return ans;
}
// Driver code
var root = new node(5);
root.left = new node(3);
root.right = new node(7);
root.left.left = new node(2);
root.left.right = new node(4);
root.right.left = new node(6);
root.right.right = new node(8);
document.write(minDiff(root));
// This code is contributed by noob2000
</script>
Python3
# Python 3 implementation of the approach import math # Node of the binary tree class node: def __init__(self, data): self.data = data self.left = None self.right = None # Function for in-order traversal of the tree def inorder(curr, prev): global ans # Base-case if (curr == None): return # Calling in-order on the left sub-tree inorder(curr.left, prev) if (prev != None): ans = min(curr.data - prev.data, ans) prev = curr # Calling in-order on the right sub-tree inorder(curr.right, prev) # Function to return the minimum # difference between any two nodes # of the given binary search tree def minDiff(root): # Pointer to previous node in the # in-order traversal of the BST prev = None # To store the final ans global ans ans = math.inf # Call in-order for the BST inorder(root, prev) # Returning the final answer return ans # Driver code if __name__ == '__main__': root = node(5) root.left = node(3) root.right = node(7) root.left.left = node(2) root.left.right = node(4) root.right.left = node(6) root.right.right = node(8) print(minDiff(root))
Producción
1
Otro enfoque con complejidad espacial O(N):
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Node of the binary tree
struct node {
int data;
node* left;
node* right;
node(int data)
{
this->data = data;
left = NULL;
right = NULL;
}
};
int absolute_diff(node* root,int target)
{
if (root == NULL)
return target;
if (root->left !=NULL)
{
int left = (root->data) - (root->left->data);
target = min(target, left);
}
if (root->right !=NULL)
{
int right = (root->right->data) - (root->data );
target = min(target, right);
}
// Find the minimum in the left subtree
int p = absolute_diff(root->left, target);
// Find the minimum in the right subtree
int q = absolute_diff(root->right, target);
return min(p, q);
}
// Driver code
int main()
{
node* root = new node(5);
root->left = new node(3);
root->right = new node(7);
root->left->left = new node(2);
root->left->right = new node(4);
root->right->left = new node(6);
root->right->right = new node(8);
cout << absolute_diff(root,INT_MAX);
return 0;
}
// This code is contributed by Arpit Jain
Java
// Java implementation of the approach
class GFG {
// Node of the binary tree
static class TreeNode {
int data;
TreeNode left;
TreeNode right;
TreeNode(int data) { this.data = data; }
}
static int target = Integer.MAX_VALUE;
// Function to find the minimum absolute difference
static int absolute_diff(TreeNode root, int target)
{
if (root == null)
return target;
if (root.left != null) {
int left = root.data - root.left.data;
target = Math.min(target, left);
}
if (root.right != null) {
int right = root.right.data - root.data;
target = Math.min(target, right);
}
// Find the minimum in the left subtree
int p = absolute_diff(root.left, target);
// Find the minimum in the right subtree
int q = absolute_diff(root.right, target);
return Math.min(p, q);
}
// Driver code
public static void main(String[] args)
{
TreeNode root = new TreeNode(5);
root.left = new TreeNode(3);
root.right = new TreeNode(7);
root.left.left = new TreeNode(2);
root.left.right = new TreeNode(4);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(8);
System.out.println(absolute_diff(root, target));
}
}
// This code is contributed by Lovely Jain
Python3
# Python 3 implementation of the approach # Node of the binary tree import math class Node: # Constructor to create a new node def __init__(self, data): self.data = data self.left = None self.right = None # Set the target to infinity target = math.inf # Function to find the minimum absolute difference def absolute_diff(root, target): if root is None: return target if root.left is not None: left = root.data-root.left.data target = min(target, left) if root.right is not None: right = root.right.data-root.data target = min(target, right) # Find the minimum in the left subtree p = absolute_diff(root.left, target) # Find the minimum in the right subtree q = absolute_diff(root.right, target) return min(p, q) # Driver code root = Node(5) root.left = Node(3) root.right = Node(7) root.left.left = Node(2) root.left.right = Node(4) root.right.left = Node(6) root.right.right = Node(8) print(absolute_diff(root, target))
Javascript
<script>
// JavaScript implementation of the approach
// Node of the binary tree
class Node{
// Constructor to create a new node
constructor(data){
this.data = data
this.left = null
this.right = null
}
}
// Set the target to infinity
let target = Number.MAX_VALUE
// Function to find the minimum absolute difference
function absolute_diff(root, target){
if(root == null)
return target
if(root.left !== null){
let left = root.data - root.left.data
target = Math.min(target, left)
}
if(root.right !== null){
let right = root.right.data - root.data
target = Math.min(target, right)
}
// Find the minimum in the left subtree
let p = absolute_diff(root.left, target)
// Find the minimum in the right subtree
let q = absolute_diff(root.right, target)
return Math.min(p, q)
}
// Driver code
let root = new Node(5)
root.left = new Node(3)
root.right = new Node(7)
root.left.left = new Node(2)
root.left.right = new Node(4)
root.right.left = new Node(6)
root.right.right = new Node(8)
document.write(absolute_diff(root,target),"</br>")
// This code is contributed by shinjanpatra
</script>
Producción
1
Complejidad temporal: O(N)
Espacio adicional: O(N) debido a la recursividad.
Publicación traducida automáticamente
Artículo escrito por DivyanshuShekhar1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA