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