Минимальный и максимальный узел, который находится на пути, соединяющем два узла в двоичном дереве
Опубликовано: 23 Января, 2022
Учитывая двоичное дерево и два узла a и b , задача состоит в том, чтобы вывести минимальное и максимальное значение узла, которое лежит на пути, соединяющем данные узлы a и b . Если какой-либо из двух узлов отсутствует в дереве, выведите -1 как для минимального, так и для максимального значения.
Примеры:
Вход:
1
/
2 3
/
4 5 6
/ /
7 8 9
а = 5, б = 6
Выход:
Мин. = 1
Макс = 6
Вход:
20
/
8 22
/ /
5 3 4 25
/
10 14
а = 5, б = 14
Выход:
Мин. = 3
Макс = 14
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Подход: идея состоит в том, чтобы найти LCA обоих узлов. Затем начните поиск минимального и максимального узла на пути от LCA к первому узлу, а затем от LCA ко второму узлу и распечатайте минимальное и максимальное из этих значений. В случае, если какой-либо из узлов отсутствует в дереве, выведите -1 для минимального, а также максимального значения.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Structure of binary treestruct Node { Node* left; Node* right; int data;};// Function to create a new nodeNode* newNode(int key){ Node* node = new Node(); node->left = node->right = NULL; node->data = key; return node;}// Function to store the path from root node// to given node of the tree in path vector and// then returns true if the path exists// otherwise falsebool FindPath(Node* root, vector<int>& path, int key){ if (root == NULL) return false; path.push_back(root->data); if (root->data == key) return true; if (FindPath(root->left, path, key) || FindPath(root->right, path, key)) return true; path.pop_back(); return false;}// Function to print the minimum and the maximum// value present in the path connecting the// given two nodes of the given binary treeint minMaxNodeInPath(Node* root, int a, int b){ // To store the path from the root node to a vector<int> Path1; // To store the path from the root node to b vector<int> Path2; // To store the minimum and the maximum value // in the path from LCA to a int min1 = INT_MAX; int max1 = INT_MIN; // To store the minimum and the maximum value // in the path from LCA to b int min2 = INT_MAX; int max2 = INT_MIN; int i = 0; int j = 0; // If both a and b are present in the tree if (FindPath(root, Path1, a) && FindPath(root, Path2, b)) { // Compare the paths to get the first different value for (i = 0; i < Path1.size() && Path2.size(); i++) if (Path1[i] != Path2[i]) break; i--; j = i; // Find minimum and maximum value // in the path from LCA to a for (; i < Path1.size(); i++) { if (min1 > Path1[i]) min1 = Path1[i]; if (max1 < Path1[i]) max1 = Path1[i]; } // Find minimum and maximum value // in the path from LCA to b for (; j < Path2.size(); j++) { if (min2 > Path2[j]) min2 = Path2[j]; if (max2 < Path2[j]) max2 = Path2[j]; } // Minimum of min values in first // path and second path cout << "Min = " << min(min1, min2) << endl; // Maximum of max values in first // path and second path cout << "Max = " << max(max1, max2); } // If no path exists else cout << "Min = -1
Max = -1";}// Driver Codeint main(){ Node* root = newNode(20); root->left = newNode(8); root->right = newNode(22); root->left->left = newNode(5); root->left->right = newNode(3); root->right->left = newNode(4); root->right->right = newNode(25); root->left->right->left = newNode(10); root->left->right->right = newNode(14); int a = 5; int b = 1454; minMaxNodeInPath(root, a, b); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG{ // Structure of binary treestatic class Node{ Node left; Node right; int data;};// Function to create a new nodestatic Node newNode(int key){ Node node = new Node(); node.left = node.right = null; node.data = key; return node;}static Vector<Integer> path;// Function to store the path from root node// to given node of the tree in path vector and// then returns true if the path exists// otherwise falsestatic boolean FindPath(Node root, int key){ if (root == null) return false; path.add(root.data); if (root.data == key) return true; if (FindPath(root.left, key) || FindPath(root.right, key)) return true; path.remove(path.size()-1); return false;}// Function to print the minimum and the maximum// value present in the path connecting the// given two nodes of the given binary treestatic int minMaxNodeInPath(Node root, int a, int b){ // To store the path from the root node to a path = new Vector<Integer> (); boolean flag = true; // To store the path from the root node to b Vector<Integer> Path2 = new Vector<Integer>(), Path1 = new Vector<Integer>(); // To store the minimum and the maximum value // in the path from LCA to a int min1 = Integer.MAX_VALUE; int max1 = Integer.MIN_VALUE; // To store the minimum and the maximum value // in the path from LCA to b int min2 = Integer.MAX_VALUE; int max2 = Integer.MIN_VALUE; int i = 0; int j = 0; flag = FindPath(root, a); Path1 = path; path = new Vector<Integer>(); flag&= FindPath(root, b); Path2 = path; // If both a and b are present in the tree if ( flag) { // Compare the paths to get the first different value for (i = 0; i < Path1.size() && i < Path2.size(); i++) if (Path1.get(i) != Path2.get(i)) break; i--; j = i; // Find minimum and maximum value // in the path from LCA to a for (; i < Path1.size(); i++) { if (min1 > Path1.get(i)) min1 = Path1.get(i); if (max1 < Path1.get(i)) max1 = Path1.get(i); } // Find minimum and maximum value // in the path from LCA to b for (; j < Path2.size(); j++) { if (min2 > Path2.get(j)) min2 = Path2.get(j); if (max2 < Path2.get(j)) max2 = Path2.get(j); } // Minimum of min values in first // path and second path System.out.println( "Min = " + Math.min(min1, min2) ); // Maximum of max values in first // path and second path System.out.println( "Max = " + Math.max(max1, max2)); } // If no path exists else System.out.println("Min = -1
Max = -1"); return 0;}// Driver Codepublic static void main(String args[]){ Node root = newNode(20); root.left = newNode(8); root.right = newNode(22); root.left.left = newNode(5); root.left.right = newNode(3); root.right.left = newNode(4); root.right.right = newNode(25); root.left.right.left = newNode(10); root.left.right.right = newNode(14); int a = 5; int b = 14; minMaxNodeInPath(root, a, b);}}// This code is contributed by Arnab Kundu |
Python3
# Python3 implementation of the approachclass Node: def __init__(self, key): self.data = key self.left = None self.right = None# Function to store the path from root# node to given node of the tree in# path vector and then returns true if# the path exists otherwise falsedef FindPath(root, path, key): if root == None: return False path.append(root.data) if root.data == key: return True if (FindPath(root.left, path, key) or FindPath(root.right, path, key)): return True path.pop() return False# Function to print the minimum and the# maximum value present in the path# connecting the given two nodes of the# given binary treedef minMaxNodeInPath(root, a, b): # To store the path from the # root node to a Path1 = [] # To store the path from the # root node to b Path2 = [] # To store the minimum and the maximum # value in the path from LCA to a min1, max1 = float("inf"), float("-inf") # To store the minimum and the maximum # value in the path from LCA to b min2, max2 = float("inf"), float("-inf") i, j = 0, 0 # If both a and b are present in the tree if (FindPath(root, Path1, a) and FindPath(root, Path2, b)): # Compare the paths to get the # first different value while i < len(Path1) and i < len(Path2): if Path1[i] != Path2[i]: break i += 1 i -= 1 j = i # Find minimum and maximum value # in the path from LCA to a while i < len(Path1): if min1 > Path1[i]: min1 = Path1[i] if max1 < Path1[i]: max1 = Path1[i] i += 1 # Find minimum and maximum value # in the path from LCA to b while j < len(Path2): if min2 > Path2[j]: min2 = Path2[j] if max2 < Path2[j]: max2 = Path2[j] j += 1 # Minimum of min values in first # path and second path print("Min =", min(min1, min2)) # Maximum of max values in first # path and second path print("Max =", max(max1, max2)) # If no path exists else: print("Min = -1
Max = -1")# Driver Codeif __name__ == "__main__": root = Node(20) root.left = Node(8) root.right = Node(22) root.left.left = Node(5) root.left.right = Node(3) root.right.left = Node(4) root.right.right = Node(25) root.left.right.left = Node(10) root.left.right.right = Node(14) a, b = 5, 14 minMaxNodeInPath(root, a, b)РЕКОМЕНДУЕМЫЕ СТАТЬИ |