Se dan un árbol binario y un número k. Imprima cada ruta en el árbol con la suma de los Nodes en la ruta como k.
Una ruta puede comenzar desde cualquier Node y terminar en cualquier Node y debe ser solo hacia abajo, es decir, no es necesario que sea un Node raíz y un Node hoja; y los números negativos también pueden estar allí en el árbol.
Ejemplos:
C++
// C++ program to print all paths with sum k. #include <bits/stdc++.h> using namespace std; // utility function to print contents of // a vector from index i to it's end void printVector(const vector<int>& v, int i) { for (int j = i; j < v.size(); j++) cout << v[j] << " "; cout << endl; } // binary tree node struct Node { int data; Node *left, *right; Node(int x) { data = x; left = right = NULL; } }; // This function prints all paths that have sum k void printKPathUtil(Node* root, vector<int>& path, int k) { // empty node if (!root) return; // add current node to the path path.push_back(root->data); // check if there's any k sum path // in the left sub-tree. printKPathUtil(root->left, path, k); // check if there's any k sum path // in the right sub-tree. printKPathUtil(root->right, path, k); // check if there's any k sum path that // terminates at this node // Traverse the entire path as // there can be negative elements too int f = 0; for (int j = path.size() - 1; j >= 0; j--) { f += path[j]; // If path sum is k, print the path if (f == k) printVector(path, j); } // Remove the current element from the path path.pop_back(); } // A wrapper over printKPathUtil() void printKPath(Node* root, int k) { vector<int> path; printKPathUtil(root, path, k); } // Driver code int main() { Node* root = new Node(1); root->left = new Node(3); root->left->left = new Node(2); root->left->right = new Node(1); root->left->right->left = new Node(1); root->right = new Node(-1); root->right->left = new Node(4); root->right->left->left = new Node(1); root->right->left->right = new Node(2); root->right->right = new Node(5); root->right->right->right = new Node(2); int k = 5; printKPath(root, k); return 0; }
Java
// Java program to print all paths with sum k. import java.util.*; class GFG { // utility function to print contents of // a vector from index i to it's end static void printVector(Vector<Integer> v, int i) { for (int j = i; j < v.size(); j++) System.out.print(v.get(j) + " "); System.out.println(); } // binary tree node static class Node { int data; Node left, right; Node(int x) { data = x; left = right = null; } }; static Vector<Integer> path = new Vector<Integer>(); // This function prints all paths that have sum k static void printKPathUtil(Node root, int k) { // empty node if (root == null) return; // add current node to the path path.add(root.data); // check if there's any k sum path // in the left sub-tree. printKPathUtil(root.left, k); // check if there's any k sum path // in the right sub-tree. printKPathUtil(root.right, k); // check if there's any k sum path that // terminates at this node // Traverse the entire path as // there can be negative elements too int f = 0; for (int j = path.size() - 1; j >= 0; j--) { f += path.get(j); // If path sum is k, print the path if (f == k) printVector(path, j); } // Remove the current element from the path path.remove(path.size() - 1); } // A wrapper over printKPathUtil() static void printKPath(Node root, int k) { path = new Vector<Integer>(); printKPathUtil(root, k); } // Driver code public static void main(String args[]) { Node root = new Node(1); root.left = new Node(3); root.left.left = new Node(2); root.left.right = new Node(1); root.left.right.left = new Node(1); root.right = new Node(-1); root.right.left = new Node(4); root.right.left.left = new Node(1); root.right.left.right = new Node(2); root.right.right = new Node(5); root.right.right.right = new Node(2); int k = 5; printKPath(root, k); } } // This code is contributed by Arnab Kundu
Python3
# Python3 program to print all paths # with sum k # utility function to print contents of # a vector from index i to it's end def printVector(v, i): for j in range(i, len(v)): print(v[j], end=" ") print() # Binary Tree Node """ utility that allocates a newNode with the given key """ class newNode: # Construct to create a newNode def __init__(self, key): self.data = key self.left = None self.right = None # This function prints all paths # that have sum k def printKPathUtil(root, path, k): # empty node if (not root): return # add current node to the path path.append(root.data) # check if there's any k sum path # in the left sub-tree. printKPathUtil(root.left, path, k) # check if there's any k sum path # in the right sub-tree. printKPathUtil(root.right, path, k) # check if there's any k sum path that # terminates at this node # Traverse the entire path as # there can be negative elements too f = 0 for j in range(len(path) - 1, -1, -1): f += path[j] # If path sum is k, print the path if (f == k): printVector(path, j) # Remove the current element # from the path path.pop(-1) # A wrapper over printKPathUtil() def printKPath(root, k): path = [] printKPathUtil(root, path, k) # Driver Code if __name__ == '__main__': root = newNode(1) root.left = newNode(3) root.left.left = newNode(2) root.left.right = newNode(1) root.left.right.left = newNode(1) root.right = newNode(-1) root.right.left = newNode(4) root.right.left.left = newNode(1) root.right.left.right = newNode(2) root.right.right = newNode(5) root.right.right.right = newNode(2) k = 5 printKPath(root, k) # This code is contributed by # Shubham Singh(SHUBHAMSINGH10)
C#
// C# program to print all paths with sum k. using System; using System.Collections.Generic; class GFG { // utility function to print contents of // a vector from index i to it's end static void printList(List<int> v, int i) { for (int j = i; j < v.Count; j++) Console.Write(v[j] + " "); Console.WriteLine(); } // binary tree node public class Node { public int data; public Node left, right; public Node(int x) { data = x; left = right = null; } }; static List<int> path = new List<int>(); // This function prints all paths that have sum k static void printKPathUtil(Node root, int k) { // empty node if (root == null) return; // add current node to the path path.Add(root.data); // check if there's any k sum path // in the left sub-tree. printKPathUtil(root.left, k); // check if there's any k sum path // in the right sub-tree. printKPathUtil(root.right, k); // check if there's any k sum path that // terminates at this node // Traverse the entire path as // there can be negative elements too int f = 0; for (int j = path.Count - 1; j >= 0; j--) { f += path[j]; // If path sum is k, print the path if (f == k) printList(path, j); } // Remove the current element from the path path.RemoveAt(path.Count - 1); } // A wrapper over printKPathUtil() static void printKPath(Node root, int k) { path = new List<int>(); printKPathUtil(root, k); } // Driver code public static void Main(String[] args) { Node root = new Node(1); root.left = new Node(3); root.left.left = new Node(2); root.left.right = new Node(1); root.left.right.left = new Node(1); root.right = new Node(-1); root.right.left = new Node(4); root.right.left.left = new Node(1); root.right.left.right = new Node(2); root.right.right = new Node(5); root.right.right.right = new Node(2); int k = 5; printKPath(root, k); } } // This code is contributed by PrinciRaj1992
Javascript
// Tree node class for Binary Tree // representation class Node { constructor(data) { this.data = data; this.left = this.right = null; } } function printPathUtil(node, k, path_arr, all_path_arr) { if (node == null) { return; } let p1 = node.data.toString(); let p2 = ''; if (path_arr.length > 0) { p2 = path_arr + ',' + p1; } else { p2 = p1; } if (node.data == k) { all_path_arr.add(p1); } let sum = 0; let p2_arr = p2.split(','); for (let i = 0; i < p2_arr.length; i++) { sum = sum + Number(p2_arr[i]); } if (sum == k) { all_path_arr.add(p2); } printPathUtil(node.left, k, p1, all_path_arr) printPathUtil(node.left, k, p2, all_path_arr) printPathUtil(node.right, k, p1, all_path_arr) printPathUtil(node.right, k, p2, all_path_arr) } function printKPath(root, k) { let all_path_arr = new Set(); printPathUtil(root, k, '', all_path_arr); return all_path_arr; } function printPaths(paths) { for (let data of paths) { document.write(data.replaceAll(',', ' ')); document.write('<br>'); } } // Driver code let root = new Node(1); root.left = new Node(3); root.left.left = new Node(2); root.left.right = new Node(1); root.left.right.left = new Node(1); root.right = new Node(-1); root.right.left = new Node(4); root.right.left.left = new Node(1); root.right.left.right = new Node(2); root.right.right = new Node(5); root.right.right.right = new Node(2); let k = 5; printPaths(printKPath(root, k)); // This code is contributed by gaurav2146
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