Dado un árbol binario , la tarea es encontrar el subárbol más pequeño que contenga todos los Nodes más profundos del árbol binario dado y devolver la raíz de ese subárbol.
Nota: La profundidad de cada Node se define como la longitud del camino desde la raíz hasta el Node dado.
Ejemplos:
Aporte:
1 / \ 2 3 / \ / \ 4 5 6 7 / \ 8 9Salida : 7
Aporte:
1 / \ 2 3Salida: 1
Enfoque: siga los pasos a continuación para resolver el problema:
- Atraviese el árbol binario recursivamente usando DFS .
- Para cada Node, encuentre la profundidad de sus subárboles izquierdo y derecho.
- Si la profundidad del subárbol izquierdo > profundidad del subárbol derecho: Atraviesa el subárbol izquierdo.
- Si la profundidad del subárbol derecho > la profundidad del subárbol izquierdo: recorrer el subárbol derecho.
- De lo contrario, devuelve el Node actual.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Structure of a Node
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int data)
{
this->val = data;
left = NULL;
right = NULL;
}
};
// Function to return depth of
// the Tree from root
int find_ht(TreeNode* root)
{
if (!root)
return 0;
// If current node is a leaf node
if (root->left == NULL
&& root->right == NULL)
return 1;
return max(find_ht(root->left),
find_ht(root->right))
+ 1;
}
// Function to find the root of the smallest
// subtree consisting of all deepest nodes
void find_node(TreeNode* root, TreeNode*& req_node)
{
if (!root)
return;
// Stores height of left subtree
int left_ht = find_ht(root->left);
// Stores height of right subtree
int right_ht = find_ht(root->right);
// If height of left subtree exceeds
// that of the right subtree
if (left_ht > right_ht) {
// Traverse left subtree
find_node(root->left, req_node);
}
// If height of right subtree exceeds
// that of the left subtree
else if (right_ht > left_ht) {
find_node(root->right, req_node);
}
// Otherwise
else {
// Return current node
req_node = root;
return;
}
}
// Driver Code
int main()
{
struct TreeNode* root
= new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
TreeNode* req_node = NULL;
find_node(root, req_node);
cout << req_node->val;
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG
{
// Structure of a Node
static class TreeNode
{
int val;
TreeNode left;
TreeNode right;
TreeNode(int data)
{
this.val = data;
left = null;
right = null;
}
};
// Function to return depth of
// the Tree from root
static int find_ht(TreeNode root)
{
if (root == null)
return 0;
// If current node is a leaf node
if (root.left == null
&& root.right == null)
return 1;
return Math.max(find_ht(root.left),
find_ht(root.right))
+ 1;
}
// Function to find the root of the smallest
// subtree consisting of all deepest nodes
static TreeNode find_node(TreeNode root, TreeNode req_node)
{
if (root == null)
return req_node;
// Stores height of left subtree
int left_ht = find_ht(root.left);
// Stores height of right subtree
int right_ht = find_ht(root.right);
// If height of left subtree exceeds
// that of the right subtree
if (left_ht > right_ht)
{
// Traverse left subtree
req_node = find_node(root.left, req_node);
}
// If height of right subtree exceeds
// that of the left subtree
else if (right_ht > left_ht)
{
req_node = find_node(root.right, req_node);
}
// Otherwise
else
{
// Return current node
req_node = root;
return req_node;
}
return req_node;
}
// Driver Code
public static void main(String[] args)
{
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
TreeNode req_node = null;
req_node = find_node(root, req_node);
System.out.print(req_node.val);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to implement # the above approach # Structure of a Node class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None # Function to return depth of # the Tree from root def find_ht(root): if (not root): return 0 # If current node is a leaf node if (root.left == None and root.right == None): return 1 return max(find_ht(root.left), find_ht(root.right)) + 1 # Function to find the root of the smallest # subtree consisting of all deepest nodes def find_node(root): global req_node if (not root): return # Stores height of left subtree left_ht = find_ht(root.left) # Stores height of right subtree right_ht = find_ht(root.right) # If height of left subtree exceeds # that of the right subtree if (left_ht > right_ht): # Traverse left subtree find_node(root.left) # If height of right subtree exceeds # that of the left subtree elif (right_ht > left_ht): find_node(root.right) # Otherwise else: # Return current node req_node = root return # Driver Code if __name__ == '__main__': root = TreeNode(1) root.left = TreeNode(2) root.right = TreeNode(3) req_node = None find_node(root) print(req_node.val) # This code is contributed by mohit kumar 29
C#
// C# program to implement
// the above approach
using System;
class GFG
{
// Structure of a Node
public class TreeNode
{
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
this.val = data;
left = null;
right = null;
}
};
// Function to return depth of
// the Tree from root
static int find_ht(TreeNode root)
{
if (root == null)
return 0;
// If current node is a leaf node
if (root.left == null
&& root.right == null)
return 1;
return Math.Max(find_ht(root.left),
find_ht(root.right))
+ 1;
}
// Function to find the root of the smallest
// subtree consisting of all deepest nodes
static TreeNode find_node(TreeNode root, TreeNode req_node)
{
if (root == null)
return req_node;
// Stores height of left subtree
int left_ht = find_ht(root.left);
// Stores height of right subtree
int right_ht = find_ht(root.right);
// If height of left subtree exceeds
// that of the right subtree
if (left_ht > right_ht)
{
// Traverse left subtree
req_node = find_node(root.left, req_node);
}
// If height of right subtree exceeds
// that of the left subtree
else if (right_ht > left_ht)
{
req_node = find_node(root.right, req_node);
}
// Otherwise
else
{
// Return current node
req_node = root;
return req_node;
}
return req_node;
}
// Driver Code
public static void Main(String[] args)
{
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
TreeNode req_node = null;
req_node = find_node(root, req_node);
Console.Write(req_node.val);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program for above approach
// Structure of a Node
class TreeNode
{
constructor(data) {
this.left = null;
this.right = null;
this.val = data;
}
}
// Function to return depth of
// the Tree from root
function find_ht(root)
{
if (root == null)
return 0;
// If current node is a leaf node
if (root.left == null
&& root.right == null)
return 1;
return Math.max(find_ht(root.left),
find_ht(root.right))
+ 1;
}
// Function to find the root of the smallest
// subtree consisting of all deepest nodes
function find_node(root, req_node)
{
if (root == null)
return req_node;
// Stores height of left subtree
let left_ht = find_ht(root.left);
// Stores height of right subtree
let right_ht = find_ht(root.right);
// If height of left subtree exceeds
// that of the right subtree
if (left_ht > right_ht)
{
// Traverse left subtree
req_node = find_node(root.left, req_node);
}
// If height of right subtree exceeds
// that of the left subtree
else if (right_ht > left_ht)
{
req_node = find_node(root.right, req_node);
}
// Otherwise
else
{
// Return current node
req_node = root;
return req_node;
}
return req_node;
}
let root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
let req_node = null;
req_node = find_node(root, req_node);
document.write(req_node.val);
</script>
Producción:
1
Complejidad de tiempo: O(NlogN)
La complejidad del peor de los casos ocurre para el árbol binario sesgado , cuyo recorrido del subárbol izquierdo o derecho requiere una complejidad O(N) y el cálculo de la altura de los subárboles requiere una complejidad computacional O(logN).
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kumargaurav8 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA