Subárbol más pequeño con todos los Nodes más profundos

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    9

Salida : 7

 

Aporte: 
 

               1
             /   \
            2     3

Salida: 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *