Imprima todas las rutas de k-sum en un árbol binario

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *