Цикл максимальной длины, который может быть сформирован путем соединения двух узлов двоичного дерева
Опубликовано: 23 Января, 2022
Для двоичного дерева задача состоит в том, чтобы найти максимальную длину цикла, который может быть сформирован путем соединения любых двух узлов дерева.
Примеры:
Вход:
1
/
2 3
5 6
Выход: 5
Цикл может быть сформирован путем присоединения узла со значением 5 и 6.
Вход:
1
/
3 4
/
5 6
/
7 8
/
11 9
Выход: 7
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Подход: Идея состоит в том, чтобы найти диаметр данного двоичного дерева, поскольку цикл с максимальной длиной будет равен диаметру двоичного дерева.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std; // Tree node structurestruct Node { int data; Node *left, *right;}; struct Node* newNode(int data){ struct Node* node = new Node; node->data = data; node->left = node->right = NULL; return (node);} // Function to find height of a treeint height(Node* root, int& ans){ if (root == NULL) return 0; int left_height = height(root->left, ans); int right_height = height(root->right, ans); // Update the answer, because diameter of a // tree is nothing but maximum value of // (left_height + right_height + 1) for each node ans = max(ans, 1 + left_height + right_height); return 1 + max(left_height, right_height);} // Computes the diameter of binary tree// with given rootint diameter(Node* root){ if (root == NULL) return 0; // Variable to store the final answer int ans = INT_MIN; int height_of_tree = height(root, ans); return ans;} // Driver codeint main(){ struct Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); printf("%d", diameter(root)); return 0;} |
Java
// Java implementation of the approachclass GFG{ // Tree node structure static class Node { int data; Node left, right; }; static int ans;static Node newNode(int data) { Node node = new Node(); node.data = data; node.left = node.right = null; return (node); } // Function to find height of a tree static int height(Node root) { if (root == null) return 0; int left_height = height(root.left); int right_height = height(root.right); // Update the answer, because diameter of a // tree is nothing but maximum value of // (left_height + right_height + 1) for each node ans = Math.max(ans, 1 + left_height + right_height); return 1 + Math.max(left_height, right_height); } // Computes the diameter of binary tree // with given root static int diameter(Node root) { if (root == null) return 0; // Variable to store the final answer ans = Integer.MIN_VALUE; int height_of_tree = height(root); return ans; } // Driver code public static void main(String[] args) { Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); System.out.printf("%d", diameter(root));}} // This code is contributed by Princi Singh |
Python3
# Python3 implementation of the approach # Tree node structure class Node: def __init__(self, data): self.data = data self.left = None self.right = None # Function to find height of a tree def height(root): if root == None: return 0 global ans left_height = height(root.left) right_height = height(root.right) # Update the answer, because diameter of a # tree is nothing but maximum value of # (left_height + right_height + 1) for each node ans = max(ans, 1 + left_height + right_height) return 1 + max(left_height, right_height) # Computes the diameter of # binary tree with given root def diameter(root): if root == None: return 0 height_of_tree = height(root) return ans # Driver code if __name__ == "__main__": root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) ans = 0 print(diameter(root)) # This code is contributed by Rituraj Jain |
C#
// C# implementation of the approachusing System; class GFG{ // Tree node structure public class Node { public int data; public Node left, right; }; static int ans;static Node newNode(int data) { Node node = new Node(); node.data = data; node.left = node.right = null; return (node); } // Function to find height of a tree static int height(Node root) { if (root == null) return 0; int left_height = height(root.left); int right_height = height(root.right); // Update the answer, because diameter of a // tree is nothing but maximum value of // (left_height + right_height + 1) for each node ans = Math.Max(ans, 1 + left_height + right_height); return 1 + Math.Max(left_height, right_height); } // Computes the diameter of binary tree // with given root static int diameter(Node root) { if (root == null) return 0; // Variable to store the final answer ans = int.MinValue; int height_of_tree = height(root); return ans; } // Driver code public static void Main(String[] args) { Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); Console.WriteLine("{0}", diameter(root));}} // This code is contributed by Rajput-Ji |
Output:
4