Dado un árbol binario , la tarea es imprimir todos los Nodes que tengan exactamente un hijo. Imprima «-1» si no existe tal Node.
Ejemplos:
Input: 2 / \ 3 5 / / \ 7 8 6 Output: 3 Explanation: There is only one node having single child that is 3. Input: 9 / \ 7 8 / \ 4 3 Output: -1 Explanation: There is no node having exactly one child in the binary tree.
Enfoque: La idea es atravesar el árbol en el recorrido en orden y en cada paso del recorrido verificar si el Node tiene exactamente un hijo. Luego agregue ese Node a una array de resultados para realizar un seguimiento de dichos Nodes. Después del recorrido, simplemente imprima cada elemento de esta array de resultados.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to print // the nodes having a single child #include <bits/stdc++.h> using namespace std; // Class of the Binary Tree node struct Node { int data; Node *left, *right; Node(int x) { data = x; left = right = NULL; } }; vector<int> lst; // Function to find the nodes // having single child void printNodesOneChild(Node* root) { // Base case if (root == NULL) return; // Condition to check if the // node is having only one child if (root->left != NULL && root->right == NULL || root->left == NULL && root->right != NULL) { lst.push_back(root->data); } // Traversing the left child printNodesOneChild(root -> left); // Traversing the right child printNodesOneChild(root -> right); } //Driver code int main() { // Constructing the binary tree Node *root = new Node(2); root -> left = new Node(3); root -> right = new Node(5); root -> left -> left = new Node(7); root -> right -> left = new Node(8); root -> right -> right = new Node(6); // Function calling printNodesOneChild(root); // Condition to check if there is // no such node having single child if (lst.size() == 0) printf("-1"); else { for(int value : lst) { cout << (value) << endl; } } } // This code is contributed by Mohit Kumar 29
Java
// Java implementation to print // the nodes having a single child import java.util.Vector; // Class of the Binary Tree node class Node { int data; Node left, right; Node(int data) { this.data = data; } } class GFG{ // List to keep track of nodes // having single child static Vector<Integer> list = new Vector<>(); // Function to find the nodes // having single child static void printNodesOneChild(Node root) { // Base case if (root == null) return; // Condition to check if the node // is having only one child if (root.left != null && root.right == null || root.left == null && root.right != null) { list.add(root.data); } // Traversing the left child printNodesOneChild(root.left); // Traversing the right child printNodesOneChild(root.right); } // Driver code public static void main(String[] args) { // Constructing the binary tree Node root = new Node(2); root.left = new Node(3); root.right = new Node(5); root.left.left = new Node(7); root.right.left = new Node(8); root.right.right = new Node(6); // Function calling printNodesOneChild(root); // Condition to check if there is // no such node having single child if (list.size() == 0) System.out.println(-1); else { for(int value : list) { System.out.println(value); } } } } // This code is contributed by sumit_9
Python3
# Python3 implementation to print # the nodes having a single child # Class of the Binary Tree node class node: # Constructor to construct # the node of the Binary tree def __init__(self, val): self.val = val self.left = None self.right = None # List to keep track of # nodes having single child single_child_nodes = [] # Function to find the nodes # having single child def printNodesOneChild(root): # Base Case if not root: return # Condition to check if the node # is having only one child if not root.left and root.right: single_child_nodes.append(root) elif root.left and not root.right: single_child_nodes.append(root) # Traversing the left child printNodesOneChild(root.left) # Traversing the right child printNodesOneChild(root.right) return # Driver Code if __name__ == "__main__": # Construction of Binary Tree root = node(2) root.left = node(3) root.right = node(5) root.left.left = node(7) root.right.left = node(8) root.right.right = node(6) # Function Call printNodesOneChild(root) # Condition to check if there is # no such node having single child if not len(single_child_nodes): print(-1) else: for i in single_child_nodes: print(i.val, end = " ") print()
C#
// C# implementation to print // the nodes having a single child using System; using System.Collections; class GFG{ // Structure of binary tree public class Node { public Node left; public Node right; public int data; }; // Function to create a new node static Node newNode(int key) { Node node = new Node(); node.left = node.right = null; node.data = key; return node; } // List to keep track of nodes // having single child static ArrayList list = new ArrayList(); // Function to find the nodes // having single child static void printNodesOneChild(Node root) { // Base case if (root == null) return; // Condition to check if the node // is having only one child if (root.left != null && root.right == null || root.left == null && root.right != null) { list.Add(root.data); } // Traversing the left child printNodesOneChild(root.left); // Traversing the right child printNodesOneChild(root.right); } // Driver code static public void Main() { // Constructing the binary tree Node root = newNode(2); root.left = newNode(3); root.right = newNode(5); root.left.left = newNode(7); root.right.left = newNode(8); root.right.right = newNode(6); // Function calling printNodesOneChild(root); // Condition to check if there is // no such node having single child if (list.Count == 0) Console.WriteLine(-1); else { foreach(int value in list) { Console.WriteLine(value); } } } } // This code is contributed by offbeat
Javascript
<script> // Javascript implementation to print // the nodes having a single child // Class of the Binary Tree node class Node { constructor(data) { this.data = data; this.left=this.right=null; } } // List to keep track of nodes // having single child let list = []; // Function to find the nodes // having single child function printNodesOneChild(root) { // Base case if (root == null) return; // Condition to check if the node // is having only one child if (root.left != null && root.right == null || root.left == null && root.right != null) { list.push(root.data); } // Traversing the left child printNodesOneChild(root.left); // Traversing the right child printNodesOneChild(root.right); } // Driver code // Constructing the binary tree let root = new Node(2); root.left = new Node(3); root.right = new Node(5); root.left.left = new Node(7); root.right.left = new Node(8); root.right.right = new Node(6); // Function calling printNodesOneChild(root); // Condition to check if there is // no such node having single child if (list.length == 0) document.write(-1); else { document.write(list.join("<br>")) } // This code is contributed by patel2127 </script>
Producción
3
Publicación traducida automáticamente
Artículo escrito por shivanshu_gupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA