Dado un árbol binario y un número k, elimine todos los Nodes que se encuentran solo en la ruta (s) de raíz a hoja de longitud menor que k. Si un Node X se encuentra en varias rutas de raíz a hoja y si alguna de las rutas tiene una longitud de ruta >= k, entonces X no se elimina del árbol binario. En otras palabras, un Node se elimina si todos los caminos que lo atraviesan tienen longitudes menores que k.
Considere el siguiente ejemplo de árbol binario
C++
// C++ program to remove nodes on root to leaf paths of length < K #include<bits/stdc++.h> using namespace std; struct Node { int data; Node *left, *right; }; //New node of a tree Node *newNode(int data) { Node *node = new Node; node->data = data; node->left = node->right = NULL; return node; } // Utility method that actually removes the nodes which are not // on the pathLen >= k. This method can change the root as well. Node *removeShortPathNodesUtil(Node *root, int level, int k) { //Base condition if (root == NULL) return NULL; // Traverse the tree in postorder fashion so that if a leaf // node path length is shorter than k, then that node and // all of its descendants till the node which are not // on some other path are removed. root->left = removeShortPathNodesUtil(root->left, level + 1, k); root->right = removeShortPathNodesUtil(root->right, level + 1, k); // If root is a leaf node and it's level is less than k then // remove this node. // This goes up and check for the ancestor nodes also for the // same condition till it finds a node which is a part of other // path(s) too. if (root->left == NULL && root->right == NULL && level < k) { delete root; return NULL; } // Return root; return root; } // Method which calls the utility method to remove the short path // nodes. Node *removeShortPathNodes(Node *root, int k) { int pathLen = 0; return removeShortPathNodesUtil(root, 1, k); } //Method to print the tree in inorder fashion. void printInorder(Node *root) { if (root) { printInorder(root->left); cout << root->data << " "; printInorder(root->right); } } // Driver method. int main() { int k = 4; Node *root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->left->left->left = newNode(7); root->right->right = newNode(6); root->right->right->left = newNode(8); cout << "Inorder Traversal of Original tree" << endl; printInorder(root); cout << endl; cout << "Inorder Traversal of Modified tree" << endl; Node *res = removeShortPathNodes(root, k); printInorder(res); return 0; }
Java
// Java program to remove nodes on root to leaf paths of length < k /* Class containing left and right child of current node and key value*/ class Node { int data; Node left, right; public Node(int item) { data = item; left = right = null; } } class BinaryTree { Node root; // Utility method that actually removes the nodes which are not // on the pathLen >= k. This method can change the root as well. Node removeShortPathNodesUtil(Node node, int level, int k) { //Base condition if (node == null) return null; // Traverse the tree in postorder fashion so that if a leaf // node path length is shorter than k, then that node and // all of its descendants till the node which are not // on some other path are removed. node.left = removeShortPathNodesUtil(node.left, level + 1, k); node.right = removeShortPathNodesUtil(node.right, level + 1, k); // If root is a leaf node and it's level is less than k then // remove this node. // This goes up and check for the ancestor nodes also for the // same condition till it finds a node which is a part of other // path(s) too. if (node.left == null && node.right == null && level < k) return null; // Return root; return node; } // Method which calls the utility method to remove the short path // nodes. Node removeShortPathNodes(Node node, int k) { int pathLen = 0; return removeShortPathNodesUtil(node, 1, k); } //Method to print the tree in inorder fashion. void printInorder(Node node) { if (node != null) { printInorder(node.left); System.out.print(node.data + " "); printInorder(node.right); } } // Driver program to test for samples public static void main(String args[]) { BinaryTree tree = new BinaryTree(); int k = 4; tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.left = new Node(4); tree.root.left.right = new Node(5); tree.root.left.left.left = new Node(7); tree.root.right.right = new Node(6); tree.root.right.right.left = new Node(8); System.out.println("The inorder traversal of original tree is : "); tree.printInorder(tree.root); Node res = tree.removeShortPathNodes(tree.root, k); System.out.println(""); System.out.println("The inorder traversal of modified tree is : "); tree.printInorder(res); } } // This code has been contributed by Mayank Jaiswal
Python3
# Python3 program to remove nodes on root # to leaf paths of length < K # New node of a tree class newNode: def __init__(self, data): self.data = data self.left = self.right = None # Utility method that actually removes # the nodes which are not on the pathLen >= k. # This method can change the root as well. def removeShortPathNodesUtil(root, level, k) : # Base condition if (root == None) : return None # Traverse the tree in postorder fashion # so that if a leaf node path length is # shorter than k, then that node and all # of its descendants till the node which # are not on some other path are removed. root.left = removeShortPathNodesUtil(root.left, level + 1, k) root.right = removeShortPathNodesUtil(root.right, level + 1, k) # If root is a leaf node and it's level # is less than k then remove this node. # This goes up and check for the ancestor # nodes also for the same condition till # it finds a node which is a part of other # path(s) too. if (root.left == None and root.right == None and level < k) : return None # Return root return root # Method which calls the utility method # to remove the short path nodes. def removeShortPathNodes(root, k) : pathLen = 0 return removeShortPathNodesUtil(root, 1, k) # Method to print the tree in # inorder fashion. def printInorder(root) : if (root) : printInorder(root.left) print(root.data, end = " " ) printInorder(root.right) # Driver Code if __name__ == '__main__': k = 4 root = newNode(1) root.left = newNode(2) root.right = newNode(3) root.left.left = newNode(4) root.left.right = newNode(5) root.left.left.left = newNode(7) root.right.right = newNode(6) root.right.right.left = newNode(8) print("Inorder Traversal of Original tree" ) printInorder(root) print() print("Inorder Traversal of Modified tree" ) res = removeShortPathNodes(root, k) printInorder(res) # This code is contributed # by SHUBHAMSINGH10
C#
using System; // C# program to remove nodes on root to leaf paths of length < k /* Class containing left and right child of current node and key value*/ public class Node { public int data; public Node left, right; public Node(int item) { data = item; left = right = null; } } public class BinaryTree { public Node root; // Utility method that actually removes the nodes which are not // on the pathLen >= k. This method can change the root as well. public virtual Node removeShortPathNodesUtil(Node node, int level, int k) { //Base condition if (node == null) { return null; } // Traverse the tree in postorder fashion so that if a leaf // node path length is shorter than k, then that node and // all of its descendants till the node which are not // on some other path are removed. node.left = removeShortPathNodesUtil(node.left, level + 1, k); node.right = removeShortPathNodesUtil(node.right, level + 1, k); // If root is a leaf node and it's level is less than k then // remove this node. // This goes up and check for the ancestor nodes also for the // same condition till it finds a node which is a part of other // path(s) too. if (node.left == null && node.right == null && level < k) { return null; } // Return root; return node; } // Method which calls the utility method to remove the short path // nodes. public virtual Node removeShortPathNodes(Node node, int k) { int pathLen = 0; return removeShortPathNodesUtil(node, 1, k); } //Method to print the tree in inorder fashion. public virtual void printInorder(Node node) { if (node != null) { printInorder(node.left); Console.Write(node.data + " "); printInorder(node.right); } } // Driver program to test for samples public static void Main(string[] args) { BinaryTree tree = new BinaryTree(); int k = 4; tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.left = new Node(4); tree.root.left.right = new Node(5); tree.root.left.left.left = new Node(7); tree.root.right.right = new Node(6); tree.root.right.right.left = new Node(8); Console.WriteLine("The inorder traversal of original tree is : "); tree.printInorder(tree.root); Node res = tree.removeShortPathNodes(tree.root, k); Console.WriteLine(""); Console.WriteLine("The inorder traversal of modified tree is : "); tree.printInorder(res); } } // This code is contributed by Shrikant13
Javascript
<script> // JavaScript program to remove nodes on // root to leaf paths of length < k class Node { constructor(item) { this.left = null; this.right = null; this.data = item; } } let root; // Utility method that actually removes the nodes which are not // on the pathLen >= k. This method can change the root as well. function removeShortPathNodesUtil(node, level, k) { //Base condition if (node == null) return null; // Traverse the tree in postorder fashion so that if a leaf // node path length is shorter than k, then that node and // all of its descendants till the node which are not // on some other path are removed. node.left = removeShortPathNodesUtil(node.left, level + 1, k); node.right = removeShortPathNodesUtil(node.right, level + 1, k); // If root is a leaf node and it's level is less than k then // remove this node. // This goes up and check for the ancestor nodes also for the // same condition till it finds a node which is a part of other // path(s) too. if (node.left == null && node.right == null && level < k) return null; // Return root; return node; } // Method which calls the utility method to remove the short path // nodes. function removeShortPathNodes(node, k) { let pathLen = 0; return removeShortPathNodesUtil(node, 1, k); } //Method to print the tree in inorder fashion. function printInorder(node) { if (node != null) { printInorder(node.left); document.write(node.data + " "); printInorder(node.right); } } let k = 4; root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); root.left.left.left = new Node(7); root.right.right = new Node(6); root.right.right.left = new Node(8); document.write("The inorder traversal of Original tree is : " + "</br>"); printInorder(root); let res = removeShortPathNodes(root, k); document.write("</br>"); document.write("The inorder traversal of Modified tree is : " + "</br>"); printInorder(res); </script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA