Dado un árbol y un Node, la tarea es invertir el camino hasta el Node dado e imprimir el recorrido en orden del árbol modificado.
Ejemplos:
Input: 7 / \ 6 5 / \ / \ 4 3 2 1 Node = 4 Output: 7 6 3 4 2 5 1 The path from root to node 4 is 7 -> 6 -> 4 Reversing this path, the modified tree will be: 4 / \ 6 5 / \ / \ 7 3 2 1 whose in-order traversal is 7 6 3 4 2 5 1 Input: 7 / \ 6 5 / \ / \ 4 3 2 1 Node = 2 Output: 4 6 3 2 7 5 1
Acercarse:
- Primero almacene todos los Nodes en la ruta dada en una cola .
- Si se encuentra la clave, reemplace los datos de este Node con los datos del frente de la cola y abra el frente.
- Siga realizando esta operación de forma recursiva hasta la raíz y la ruta se invertirá en el árbol original.
- Ahora, imprima el recorrido en orden del árbol modificado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // A Binary Tree Node struct Node { int data; struct Node *left, *right; }; // Function to reverse the tree path queue<int> reverseTreePathUtil(Node* root, int data, queue<int> q1) { queue<int> emptyQueue; // If root is null then return // an empty queue if (root == NULL) return emptyQueue; // If the node is found if (root->data == data) { // Replace it with the queue's front q1.push(root->data); root->data = q1.front(); q1.pop(); return q1; } // Push data into the queue for // storing data from start to end q1.push(root->data); // If the returned queue is empty then // it means that the left sub-tree doesn't // contain the required node queue<int> left = reverseTreePathUtil(root->left, data, q1); // If the returned queue is empty then // it means that the right sub-tree doesn't // contain the required node queue<int> right = reverseTreePathUtil(root->right, data, q1); // If the required node is found // in the right sub-tree if (!right.empty()) { // Replace with the queue's front root->data = right.front(); right.pop(); return right; } // If the required node is found // in the right sub-tree if (!left.empty()) { // Replace with the queue's front root->data = left.front(); left.pop(); return left; } // Return emptyQueue if path // is not found return emptyQueue; } // Function to call reverseTreePathUtil // to reverse the tree path void reverseTreePath(Node* root, int data) { queue<int> q1; // reverse tree path reverseTreePathUtil(root, data, q1); } // Function to print the in-order // traversal of the tree void inorder(Node* root) { if (root != NULL) { inorder(root->left); cout << root->data << " "; inorder(root->right); } } // Utility function to create a new tree node Node* newNode(int data) { Node* temp = new Node; temp->data = data; temp->left = temp->right = NULL; return temp; } // Driver code int main() { Node* root = newNode(7); root->left = newNode(6); root->right = newNode(5); root->left->left = newNode(4); root->left->right = newNode(3); root->right->left = newNode(2); root->right->right = newNode(1); int data = 4; // Function call to reverse the path reverseTreePath(root, data); // Print the in-order traversal // of the modified tree inorder(root); return 0; }
Java
// Java implementation of the approach import java.util.*; public class Main { // A Binary Tree Node static class Node { public int data; public Node left, right; public Node(int data) { this.data = data; left = right = null; } } // Function to reverse the tree path static Vector<Integer> reverseTreePathUtil(Node root, int data, Vector<Integer> q1) { Vector<Integer> emptyQueue = new Vector<Integer>(); // If root is null then return // an empty queue if (root == null) return emptyQueue; // If the node is found if (root.data == data) { // Replace it with the queue's front q1.add(root.data); root.data = q1.get(0); q1.remove(0); return q1; } // Push data into the queue for // storing data from start to end q1.add(root.data); // If the returned queue is empty then // it means that the left sub-tree doesn't // contain the required node Vector<Integer> left = reverseTreePathUtil(root.left, data, q1); // If the returned queue is empty then // it means that the right sub-tree doesn't // contain the required node Vector<Integer> right = reverseTreePathUtil(root.right, data, q1); // If the required node is found // in the right sub-tree if (right.size() > 0) { // Replace with the queue's front root.data = right.get(0); right.remove(0); return right; } // If the required node is found // in the right sub-tree if (left.size() > 0) { // Replace with the queue's front root.data = left.get(0); left.remove(0); return left; } // Return emptyQueue if path // is not found return emptyQueue; } // Function to call reverseTreePathUtil // to reverse the tree path static void reverseTreePath(Node root, int data) { Vector<Integer> q1 = new Vector<Integer>(); // reverse tree path reverseTreePathUtil(root, data, q1); } // Function to print the in-order // traversal of the tree static void inorder(Node root) { if (root != null) { inorder(root.left); System.out.print(root.data + " "); inorder(root.right); } } // Utility function to create a new tree node static Node newNode(int data) { Node temp = new Node(data); return temp; } public static void main(String[] args) { // Driver code Node root = newNode(7); root.left = newNode(6); root.right = newNode(5); root.left.left = newNode(4); root.left.right = newNode(3); root.right.left = newNode(2); root.right.right = newNode(1); int data = 4; // Function call to reverse the path reverseTreePath(root, data); // Print the in-order traversal // of the modified tree inorder(root); } } // This code is contributed by divyesh072019.
Python3
# Python3 implementation of the # above approach # A Binary Tree Node class Node: def __init__(self, data): self.data = data self.left = None self.right = None # Function to reverse the # tree path def reverseTreePathUtil(root, data, q1): emptyQueue = [] # If root is null then # return an empty queue if (root == None): return emptyQueue; # If the node is found if (root.data == data): # Replace it with the # queue's front q1.append(root.data); root.data = q1[0] q1.pop(0); return q1; # Push data into the # queue for storing # data from start to end q1.append(root.data); # If the returned queue # is empty then it means # that the left sub-tree # doesn't contain the # required node left = reverseTreePathUtil(root.left, data, q1); # If the returned queue is empty # then it means that the right # sub-tree doesn't contain the # required node right = reverseTreePathUtil(root.right, data, q1); # If the required node is found # in the right sub-tree if len(right) != 0: # Replace with the queue's # front root.data = right[0] right.pop(0); return right; # If the required node # is found in the right # sub-tree if len(left) != 0: # Replace with the # queue's front root.data = left[0] left.pop(0); return left; # Return emptyQueue # if path is not found return emptyQueue; # Function to call reverseTreePathUtil # to reverse the tree path def reverseTreePath(root, data): q1 = [] # reverse tree path reverseTreePathUtil(root, data, q1); # Function to print the in-order # traversal of the tree def inorder(root): if (root != None): inorder(root.left); print(root.data, end = ' ') inorder(root.right); # Utility function to create # a new tree node def newNode(data): temp = Node(data) return temp; # Driver code if __name__ == "__main__": root = newNode(7); root.left = newNode(6); root.right = newNode(5); root.left.left = newNode(4); root.left.right = newNode(3); root.right.left = newNode(2); root.right.right = newNode(1); data = 4; # Function call to reverse # the path reverseTreePath(root, data); # Print the in-order traversal # of the modified tree inorder(root); # This code is contributed by Rutvik_56
C#
// C# implementation of the approach using System; using System.Collections.Generic; class GFG { // A Binary Tree Node class Node { public int data; public Node left, right; public Node(int data) { this.data = data; left = right = null; } } // Function to reverse the tree path static List<int> reverseTreePathUtil(Node root, int data, List<int> q1) { List<int> emptyQueue = new List<int>(); // If root is null then return // an empty queue if (root == null) return emptyQueue; // If the node is found if (root.data == data) { // Replace it with the queue's front q1.Add(root.data); root.data = q1[0]; q1.RemoveAt(0); return q1; } // Push data into the queue for // storing data from start to end q1.Add(root.data); // If the returned queue is empty then // it means that the left sub-tree doesn't // contain the required node List<int> left = reverseTreePathUtil(root.left, data, q1); // If the returned queue is empty then // it means that the right sub-tree doesn't // contain the required node List<int> right = reverseTreePathUtil(root.right, data, q1); // If the required node is found // in the right sub-tree if (right.Count > 0) { // Replace with the queue's front root.data = right[0]; right.RemoveAt(0); return right; } // If the required node is found // in the right sub-tree if (left.Count > 0) { // Replace with the queue's front root.data = left[0]; left.RemoveAt(0); return left; } // Return emptyQueue if path // is not found return emptyQueue; } // Function to call reverseTreePathUtil // to reverse the tree path static void reverseTreePath(Node root, int data) { List<int> q1 = new List<int>(); // reverse tree path reverseTreePathUtil(root, data, q1); } // Function to print the in-order // traversal of the tree static void inorder(Node root) { if (root != null) { inorder(root.left); Console.Write(root.data + " "); inorder(root.right); } } // Utility function to create a new tree node static Node newNode(int data) { Node temp = new Node(data); return temp; } static void Main() { // Driver code Node root = newNode(7); root.left = newNode(6); root.right = newNode(5); root.left.left = newNode(4); root.left.right = newNode(3); root.right.left = newNode(2); root.right.right = newNode(1); int data = 4; // Function call to reverse the path reverseTreePath(root, data); // Print the in-order traversal // of the modified tree inorder(root); } } // This code is contributed by mukesh07.
Javascript
<script> // Javascript implementation of the approach // A Binary Tree Node class Node { constructor(data) { this.left = null; this.right = null; this.data = data; } } // Function to reverse the tree path function reverseTreePathUtil(root, data, q1) { let emptyQueue = []; // If root is null then return // an empty queue if (root == null) return emptyQueue; // If the node is found if (root.data == data) { // Replace it with the queue's front q1.push(root.data); root.data = q1[0]; q1.shift(); return q1; } // Push data into the queue for // storing data from start to end q1.push(root.data); // If the returned queue is empty then // it means that the left sub-tree doesn't // contain the required node let left = reverseTreePathUtil(root.left, data, q1); // If the returned queue is empty then // it means that the right sub-tree doesn't // contain the required node let right = reverseTreePathUtil(root.right, data, q1); // If the required node is found // in the right sub-tree if (right.length > 0) { // Replace with the queue's front root.data = right[0]; right.shift(); return right; } // If the required node is found // in the right sub-tree if (left.length > 0) { // Replace with the queue's front root.data = left[0]; left.shift(); return left; } // Return emptyQueue if path // is not found return emptyQueue; } // Function to call reverseTreePathUtil // to reverse the tree path function reverseTreePath(root, data) { let q1 = []; // Reverse tree path reverseTreePathUtil(root, data, q1); } // Function to print the in-order // traversal of the tree function inorder(root) { if (root != null) { inorder(root.left); document.write(root.data + " "); inorder(root.right); } } // Utility function to create a new tree node function newNode(data) { let temp = new Node(data); return temp; } // Driver code let root = newNode(7); root.left = newNode(6); root.right = newNode(5); root.left.left = newNode(4); root.left.right = newNode(3); root.right.left = newNode(2); root.right.right = newNode(1); let data = 4; // Function call to reverse the path reverseTreePath(root, data); // Print the in-order traversal // of the modified tree inorder(root); // This code is contributed by divyeshrabadiya07 </script>
Producción:
7 6 3 4 2 5 1
Publicación traducida automáticamente
Artículo escrito por DevanshuAgarwal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA