Dada la raíz de un árbol binario y una clave x en él, encuentre la distancia de la clave dada desde la raíz. Distancia significa el número de aristas entre dos Nodes.
Ejemplos:
C++
// C++ program to find distance of a given
// node from root.
#include <bits/stdc++.h>
using namespace std;
// A Binary Tree Node
struct Node
{
int data;
Node *left, *right;
};
// A utility function to create a new Binary
// Tree Node
Node *newNode(int item)
{
Node *temp = new Node;
temp->data = item;
temp->left = temp->right = NULL;
return temp;
}
// Returns -1 if x doesn't exist in tree. Else
// returns distance of x from root
int findDistance(Node *root, int x)
{
// Base case
if (root == NULL)
return -1;
// Initialize distance
int dist = -1;
// Check if x is present at root or in left
// subtree or right subtree.
if ((root->data == x) ||
(dist = findDistance(root->left, x)) >= 0 ||
(dist = findDistance(root->right, x)) >= 0)
return dist + 1;
return dist;
}
// Driver Program to test above functions
int main()
{
Node *root = newNode(5);
root->left = newNode(10);
root->right = newNode(15);
root->left->left = newNode(20);
root->left->right = newNode(25);
root->left->right->right = newNode(45);
root->right->left = newNode(30);
root->right->right = newNode(35);
cout << findDistance(root, 45);
return 0;
}
Java
// Java program to find distance of a given
// node from root.
import java.util.*;
class GfG {
// A Binary Tree Node
static class Node
{
int data;
Node left, right;
}
// A utility function to create a new Binary
// Tree Node
static Node newNode(int item)
{
Node temp = new Node();
temp.data = item;
temp.left = null;
temp.right = null;
return temp;
}
// Returns -1 if x doesn't exist in tree. Else
// returns distance of x from root
static int findDistance(Node root, int x)
{
// Base case
if (root == null)
return -1;
// Initialize distance
int dist = -1;
// Check if x is present at root or in left
// subtree or right subtree.
if ((root.data == x) ||
(dist = findDistance(root.left, x)) >= 0 ||
(dist = findDistance(root.right, x)) >= 0)
return dist + 1;
return dist;
}
// Driver Program to test above functions
public static void main(String[] args)
{
Node root = newNode(5);
root.left = newNode(10);
root.right = newNode(15);
root.left.left = newNode(20);
root.left.right = newNode(25);
root.left.right.right = newNode(45);
root.right.left = newNode(30);
root.right.right = newNode(35);
System.out.println(findDistance(root, 45));
}
}
Python3
# Python3 program to find distance of # a given node from root. # A class to create a new Binary # Tree Node class newNode: def __init__(self, item): self.data = item self.left = self.right = None # Returns -1 if x doesn't exist in tree. # Else returns distance of x from root def findDistance(root, x): # Base case if (root == None): return -1 # Initialize distance dist = -1 # Check if x is present at root or # in left subtree or right subtree. if (root.data == x): return dist + 1 else: dist = findDistance(root.left, x) if dist >= 0: return dist + 1 else: dist = findDistance(root.right, x) if dist >= 0: return dist + 1 return dist # Driver Code if __name__ == '__main__': root = newNode(5) root.left = newNode(10) root.right = newNode(15) root.left.left = newNode(20) root.left.right = newNode(25) root.left.right.right = newNode(45) root.right.left = newNode(30) root.right.right = newNode(35) print(findDistance(root, 45)) # This code is contributed by PranchalK
C#
// C# program to find distance of a given
// node from root.
using System;
class GfG
{
// A Binary Tree Node
class Node
{
public int data;
public Node left, right;
}
// A utility function to create
// a new Binary Tree Node
static Node newNode(int item)
{
Node temp = new Node();
temp.data = item;
temp.left = null;
temp.right = null;
return temp;
}
// Returns -1 if x doesn't exist in tree. Else
// returns distance of x from root
static int findDistance(Node root, int x)
{
// Base case
if (root == null)
return -1;
// Initialize distance
int dist = -1;
// Check if x is present at root or in left
// subtree or right subtree.
if ((root.data == x) ||
(dist = findDistance(root.left, x)) >= 0 ||
(dist = findDistance(root.right, x)) >= 0)
return dist + 1;
return dist;
}
// Driver code
public static void Main(String[] args)
{
Node root = newNode(5);
root.left = newNode(10);
root.right = newNode(15);
root.left.left = newNode(20);
root.left.right = newNode(25);
root.left.right.right = newNode(45);
root.right.left = newNode(30);
root.right.right = newNode(35);
Console.WriteLine(findDistance(root, 45));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to find distance
// of a given node from root.
// A Binary Tree Node
class Node
{
// A utility function to create a
// new Binary Tree Node
constructor(data)
{
this.data = data;
this.left = this.right = null;
}
}
// Returns -1 if x doesn't exist in tree. Else
// returns distance of x from root
function findDistance(root, x)
{
// Base case
if (root == null)
return -1;
// Initialize distance
let dist = -1;
// Check if x is present at root or in left
// subtree or right subtree.
if ((root.data == x) ||
(dist = findDistance(root.left, x)) >= 0 ||
(dist = findDistance(root.right, x)) >= 0)
return dist + 1;
return dist;
}
// Driver code
let root = new Node(5);
root.left = new Node(10);
root.right = new Node(15);
root.left.left = new Node(20);
root.left.right = new Node(25);
root.left.right.right = new Node(45);
root.right.left = new Node(30);
root.right.right = new Node(35);
document.write(findDistance(root, 45));
// This code is contributed by rag2127
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA