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