Dado un árbol binario que consiste en N Nodes que tienen valores distintos del rango [1, N] , la tarea es encontrar el ancestro común más bajo de las hojas más profundas del árbol binario.
Ejemplos:
Aporte:
Salida: 1
Explicación: Los Nodes de hoja más profundos del árbol son {8, 9, 10}. El ancestro común más bajo de estos Nodes es 1.Aporte:
Salida: 6
Enfoque: El problema dado se puede resolver encontrando la profundidad máxima del árbol y luego realizando el DFS Traversal para encontrar el ancestro común más bajo . Siga los pasos a continuación para resolver el problema:
- Encuentre la profundidad máxima de un árbol binario y guárdela en una variable, digamos depth .
- Declare una función , digamos DFS (root, curr) para encontrar el LCS de los Nodes en el nivel de profundidad :
- Si la raíz es NULL , devuelve NULL .
- Si el valor de curr es igual a depth , devuelve el Node actual.
- Llame recursivamente al subárbol izquierdo como DFS (root⇾left, curr + 1) y almacene el valor devuelto en una variable, digamos left .
- Llame recursivamente al subárbol derecho como DFS (root⇾right, curr + 1) y almacene el valor devuelto en una variable, digamos right .
- Si el valor de la izquierda y la derecha son NOT NULL , devuelve el Node actual como el Node actual es el ancestro común más bajo.
- Si la izquierda NO es NULL , entonces regresa a la izquierda . De lo contrario, regresa a la derecha .
- Después de completar los pasos anteriores, imprima el valor devuelto por la llamada de función DFS(root, 0) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Node of a Binary Tree
struct Node {
struct Node* left;
struct Node* right;
int data;
};
// Function to create
// a new tree Node
Node* newNode(int key)
{
Node* temp = new Node;
temp->data = key;
temp->left = temp->right = NULL;
return temp;
}
// Function to find the depth
// of the Binary Tree
int finddepth(Node* root)
{
// If root is not null
if (!root)
return 0;
// Left recursive subtree
int left = finddepth(root->left);
// Right recursive subtree
int right = finddepth(root->right);
// Returns the maximum depth
return 1 + max(left, right);
}
// Function to perform the depth
// first search on the binary tree
Node* dfs(Node* root, int curr,
int depth)
{
// If root is null
if (!root)
return NULL;
// If curr is equal to depth
if (curr == depth)
return root;
// Left recursive subtree
Node* left = dfs(root->left,
curr + 1, depth);
// Right recursive subtree
Node* right = dfs(root->right,
curr + 1, depth);
// If left and right are not null
if (left != NULL && right != NULL)
return root;
// Return left, if left is not null
// Otherwise return right
return left ? left : right;
}
// Function to find the LCA of the
// deepest nodes of the binary tree
Node* lcaOfDeepestLeaves(Node* root)
{
// If root is null
if (!root)
return NULL;
// Stores the deepest depth
// of the binary tree
int depth = finddepth(root) - 1;
// Return the LCA of the
// nodes at level depth
return dfs(root, 0, depth);
}
// Driver Code
int main()
{
// Given Binary Tree
Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);
root->right->left->left = newNode(8);
root->right->left->right = newNode(9);
cout << lcaOfDeepestLeaves(root)->data;
return 0;
}
Java
// Java program for the above approach
// Node of a Binary Tree
class Node
{
Node left = null;
Node right = null;
int data;
Node(int data)
{
this.data = data;
}
}
class GFG{
// Function to find the depth
// of the Binary Tree
public static int findDepth(Node root)
{
// If root is not null
if (root == null)
return 0;
// Left recursive subtree
int left = findDepth(root.left);
// Right recursive subtree
int right = findDepth(root.right);
// Returns the maximum depth
return 1 + Math.max(left, right);
}
// Function to perform the depth
// first search on the binary tree
public static Node DFS(Node root, int curr,
int depth)
{
// If root is null
if (root == null)
return null;
// If curr is equal to depth
if (curr == depth)
return root;
// Left recursive subtree
Node left = DFS(root.left, curr + 1, depth);
// Right recursive subtree
Node right = DFS(root.right, curr + 1, depth);
// If left and right are not null
if (left != null && right != null)
return root;
// Return left, if left is not null
// Otherwise return right
return (left != null) ? left : right;
}
// Function to find the LCA of the
// deepest nodes of the binary tree
public static Node lcaOfDeepestLeaves(Node root)
{
// If root is null
if (root == null)
return null;
// Stores the deepest depth
// of the binary tree
int depth = findDepth(root) - 1;
// Return the LCA of the
// nodes at level depth
return DFS(root, 0, depth);
}
// Driver code
public static void main(String[] args)
{
// Given Binary Tree
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
root.right.left.left = new Node(8);
root.right.left.right = new Node(9);
System.out.println(lcaOfDeepestLeaves(root).data);
}
}
// This code is contributed by girishthatte
Python3
# Python3 program for the above approach # Node of a Binary Tree class Node: def __init__(self, d): self.data = d self.left = None self.right = None # Function to find the depth # of the Binary Tree def finddepth(root): # If root is not null if (not root): return 0 # Left recursive subtree left = finddepth(root.left) # Right recursive subtree right = finddepth(root.right) # Returns the maximum depth return 1 + max(left, right) # Function to perform the depth # first search on the binary tree def dfs(root, curr, depth): # If root is null if (not root): return None # If curr is equal to depth if (curr == depth): return root # Left recursive subtree left = dfs(root.left, curr + 1, depth) # Right recursive subtree right = dfs(root.right, curr + 1, depth) # If left and right are not null if (left != None and right != None): return root # Return left, if left is not null # Otherwise return right return left if left else right # Function to find the LCA of the # deepest nodes of the binary tree def lcaOfDeepestLeaves(root): # If root is null if (not root): return None # Stores the deepest depth # of the binary tree depth = finddepth(root) - 1 # Return the LCA of the # nodes at level depth return dfs(root, 0, depth) # Driver Code if __name__ == '__main__': # Given Binary Tree root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.right.left = Node(6) root.right.right = Node(7) root.right.left.left = Node(8) root.right.left.right = Node(9) print(lcaOfDeepestLeaves(root).data) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
// Node of a Binary Tree
class Node
{
public Node left = null;
public Node right = null;
public int data;
public Node(int data)
{
this.data = data;
}
}
public class GFG{
// Function to find the depth
// of the Binary Tree
static int findDepth(Node root)
{
// If root is not null
if (root == null)
return 0;
// Left recursive subtree
int left = findDepth(root.left);
// Right recursive subtree
int right = findDepth(root.right);
// Returns the maximum depth
return 1 + Math.Max(left, right);
}
// Function to perform the depth
// first search on the binary tree
static Node DFS(Node root, int curr,
int depth)
{
// If root is null
if (root == null)
return null;
// If curr is equal to depth
if (curr == depth)
return root;
// Left recursive subtree
Node left = DFS(root.left, curr + 1, depth);
// Right recursive subtree
Node right = DFS(root.right, curr + 1, depth);
// If left and right are not null
if (left != null && right != null)
return root;
// Return left, if left is not null
// Otherwise return right
return (left != null) ? left : right;
}
// Function to find the LCA of the
// deepest nodes of the binary tree
static Node lcaOfDeepestLeaves(Node root)
{
// If root is null
if (root == null)
return null;
// Stores the deepest depth
// of the binary tree
int depth = findDepth(root) - 1;
// Return the LCA of the
// nodes at level depth
return DFS(root, 0, depth);
}
// Driver code
public static void Main(String[] args)
{
// Given Binary Tree
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
root.right.left.left = new Node(8);
root.right.left.right = new Node(9);
Console.WriteLine(lcaOfDeepestLeaves(root).data);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program for the above approach
// Node of a Binary Tree
class Node
{
constructor(data) {
this.left = null;
this.right = null;
this.data = data;
}
}
// Function to find the depth
// of the Binary Tree
function findDepth(root)
{
// If root is not null
if (root == null)
return 0;
// Left recursive subtree
let left = findDepth(root.left);
// Right recursive subtree
let right = findDepth(root.right);
// Returns the maximum depth
return 1 + Math.max(left, right);
}
// Function to perform the depth
// first search on the binary tree
function DFS(root, curr, depth)
{
// If root is null
if (root == null)
return null;
// If curr is equal to depth
if (curr == depth)
return root;
// Left recursive subtree
let left = DFS(root.left, curr + 1, depth);
// Right recursive subtree
let right = DFS(root.right, curr + 1, depth);
// If left and right are not null
if (left != null && right != null)
return root;
// Return left, if left is not null
// Otherwise return right
return (left != null) ? left : right;
}
// Function to find the LCA of the
// deepest nodes of the binary tree
function lcaOfDeepestLeaves(root)
{
// If root is null
if (root == null)
return null;
// Stores the deepest depth
// of the binary tree
let depth = findDepth(root) - 1;
// Return the LCA of the
// nodes at level depth
return DFS(root, 0, depth);
}
// Given Binary Tree
let root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
root.right.left.left = new Node(8);
root.right.left.right = new Node(9);
document.write(lcaOfDeepestLeaves(root).data);
// This code is contributed by suresh07.
</script>
Producción:
6
Complejidad de tiempo: O(N), donde N es el número total de Nodes en el árbol binario.
Espacio Auxiliar: O(N), ya que se ha tomado N espacio extra.
Publicación traducida automáticamente
Artículo escrito por rahulagarwal14 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA