Dado un árbol binario, donde cada valor de Node es un dígito del 1 al 9. Encuentre la suma de todos los números que se forman desde la raíz hasta la hoja.
Por ejemplo, considere el siguiente árbol binario.
6
/ \
3 5
/ \ \
2 5 4
/ \
7 4
There are 4 leaves, hence 4 root to leaf paths:
Path Number
6->3->2 632
6->3->5->7 6357
6->3->5->4 6354
6->5>4 654
Answer = 632 + 6357 + 6354 + 654 = 13997
La idea es hacer un recorrido de preorden del árbol. En el recorrido de preorden, realice un seguimiento del valor calculado hasta el Node actual, deje que este valor sea val . Para cada Node, actualizamos el val como val*10 más los datos del Node.
C++
// C++ program to find sum of
// all paths from root to leaves
#include <bits/stdc++.h>
using namespace std;
class node
{
public:
int data;
node *left, *right;
};
// function to allocate new node with given data
node* newNode(int data)
{
node* Node = new node();
Node->data = data;
Node->left = Node->right = NULL;
return (Node);
}
// Returns sum of all root to leaf paths.
// The first parameter is root
// of current subtree, the second
// parameter is value of the number formed
// by nodes from root to this node
int treePathsSumUtil(node *root, int val)
{
// Base case
if (root == NULL) return 0;
// Update val
val = (val*10 + root->data);
// if current node is leaf, return the current value of val
if (root->left==NULL && root->right==NULL)
return val;
// recur sum of values for left and right subtree
return treePathsSumUtil(root->left, val) +
treePathsSumUtil(root->right, val);
}
// A wrapper function over treePathsSumUtil()
int treePathsSum(node *root)
{
// Pass the initial value as 0
// as there is nothing above root
return treePathsSumUtil(root, 0);
}
// Driver code
int main()
{
node *root = newNode(6);
root->left = newNode(3);
root->right = newNode(5);
root->left->left = newNode(2);
root->left->right = newNode(5);
root->right->right = newNode(4);
root->left->right->left = newNode(7);
root->left->right->right = newNode(4);
cout<<"Sum of all paths is "<<treePathsSum(root);
return 0;
}
// This code is contributed by rathbhupendra
C
// C program to find sum of all paths from root to leaves
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *left, *right;
};
// function to allocate new node with given data
struct node* newNode(int data)
{
struct node* node = (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = node->right = NULL;
return (node);
}
// Returns sum of all root to leaf paths. The first parameter is root
// of current subtree, the second parameter is value of the number formed
// by nodes from root to this node
int treePathsSumUtil(struct node *root, int val)
{
// Base case
if (root == NULL) return 0;
// Update val
val = (val*10 + root->data);
// if current node is leaf, return the current value of val
if (root->left==NULL && root->right==NULL)
return val;
// recur sum of values for left and right subtree
return treePathsSumUtil(root->left, val) +
treePathsSumUtil(root->right, val);
}
// A wrapper function over treePathsSumUtil()
int treePathsSum(struct node *root)
{
// Pass the initial value as 0 as there is nothing above root
return treePathsSumUtil(root, 0);
}
// Driver function to test the above functions
int main()
{
struct node *root = newNode(6);
root->left = newNode(3);
root->right = newNode(5);
root->left->left = newNode(2);
root->left->right = newNode(5);
root->right->right = newNode(4);
root->left->right->left = newNode(7);
root->left->right->right = newNode(4);
printf("Sum of all paths is %d", treePathsSum(root));
return 0;
}
Java
// Java program to find sum of all numbers that are formed from root
// to leaf paths
// A binary tree node
class Node
{
int data;
Node left, right;
Node(int item)
{
data = item;
left = right = null;
}
}
class BinaryTree
{
Node root;
// Returns sum of all root to leaf paths. The first parameter is
// root of current subtree, the second parameter is value of the
// number formed by nodes from root to this node
int treePathsSumUtil(Node node, int val)
{
// Base case
if (node == null)
return 0;
// Update val
val = (val * 10 + node.data);
// if current node is leaf, return the current value of val
if (node.left == null && node.right == null)
return val;
// recur sum of values for left and right subtree
return treePathsSumUtil(node.left, val)
+ treePathsSumUtil(node.right, val);
}
// A wrapper function over treePathsSumUtil()
int treePathsSum(Node node)
{
// Pass the initial value as 0 as there is nothing above root
return treePathsSumUtil(node, 0);
}
// Driver program to test above functions
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(6);
tree.root.left = new Node(3);
tree.root.right = new Node(5);
tree.root.right.right = new Node(4);
tree.root.left.left = new Node(2);
tree.root.left.right = new Node(5);
tree.root.left.right.right = new Node(4);
tree.root.left.right.left = new Node(7);
System.out.print("Sum of all paths is " +
tree.treePathsSum(tree.root));
}
}
// This code has been contributed by Mayank Jaiswal
Python3
# Python program to find sum of all paths from root to leaves
# A Binary tree node
class Node:
# Constructor to create a new node
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# Returns sums of all root to leaf paths. The first parameter is root
# of current subtree, the second paramete"r is value of the number
# formed by nodes from root to this node
def treePathsSumUtil(root, val):
# Base Case
if root is None:
return 0
# Update val
val = (val*10 + root.data)
# If current node is leaf, return the current value of val
if root.left is None and root.right is None:
return val
# Recur sum of values for left and right subtree
return (treePathsSumUtil(root.left, val) +
treePathsSumUtil(root.right, val))
# A wrapper function over treePathSumUtil()
def treePathsSum(root):
# Pass the initial value as 0 as ther is nothing above root
return treePathsSumUtil(root, 0)
# Driver function to test above function
root = Node(6)
root.left = Node(3)
root.right = Node(5)
root.left.left = Node(2)
root.left.right = Node(5)
root.right.right = Node(4)
root.left.right.left = Node(7)
root.left.right.right = Node(4)
print ("Sum of all paths is", treePathsSum(root))
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)
C#
// c# program to find sum of all numbers
// that are formed from root to leaf paths
using System;
// A binary tree node
public class Node
{
public int data;
public Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
class GFG
{
public Node root;
// Returns sum of all root to leaf paths.
// The first parameter is root of current
// subtree, the second parameter is value
// of the number formed by nodes from root
// to this node
public virtual int treePathsSumUtil(Node node,
int val)
{
// Base case
if (node == null)
{
return 0;
}
// Update val
val = (val * 10 + node.data);
// if current node is leaf, return
// the current value of val
if (node.left == null && node.right == null)
{
return val;
}
// recur sum of values for left and right subtree
return treePathsSumUtil(node.left, val) +
treePathsSumUtil(node.right, val);
}
// A wrapper function over treePathsSumUtil()
public virtual int treePathsSum(Node node)
{
// Pass the initial value as 0 as
// there is nothing above root
return treePathsSumUtil(node, 0);
}
// Driver Code
public static void Main(string[] args)
{
GFG tree = new GFG();
tree.root = new Node(6);
tree.root.left = new Node(3);
tree.root.right = new Node(5);
tree.root.right.right = new Node(4);
tree.root.left.left = new Node(2);
tree.root.left.right = new Node(5);
tree.root.left.right.right = new Node(4);
tree.root.left.right.left = new Node(7);
Console.Write("Sum of all paths is " +
tree.treePathsSum(tree.root));
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// JavaScript program to find sum of
// all paths from root to leaves
class node
{
constructor(data){
this.data = data;
this.left = this.right = null;
}
}
// Returns sum of all root to leaf paths.
// The first parameter is root
// of current subtree, the second
// parameter is value of the number formed
// by nodes from root to this node
function treePathsSumUtil(root,val)
{
// Base case
if (root == null) return 0;
// Update val
val = (val*10 + root.data);
// if current node is leaf, return the current value of val
if (root.left==null && root.right==null)
return val;
// recur sum of values for left and right subtree
return treePathsSumUtil(root.left, val) + treePathsSumUtil(root.right, val);
}
// A wrapper function over treePathsSumUtil()
function treePathsSum(root)
{
// Pass the initial value as 0
// as there is nothing above root
return treePathsSumUtil(root, 0);
}
// Driver code
let root = new node(6);
root.left = new node(3);
root.right = new node(5);
root.left.left = new node(2);
root.left.right = new node(5);
root.right.right = new node(4);
root.left.right.left = new node(7);
root.left.right.right = new node(4);
document.write("Sum of all paths is "+treePathsSum(root));
// This code is contributed by shinjanpatra
</script>
C++
// C++ program to find sum of all paths from root to leaves
// A Binary tree node
#include <bits/stdc++.h>
using namespace std;
// A Binary tree node
class Node
{
public:
int data;
Node *left, *right;
// Constructor to create a new node
Node(int val)
{
data = val;
left = right = NULL;
}
};
void treePathsSumUtil(Node* root, vector<string> currPath,
vector<vector<string>> &allPath)
{
// Base Case
if (root == NULL)
return;
// append the root data in string format in currPath
currPath.push_back((to_string)(root->data));
// if we found a leaf node we copy the the currPath to allPath
if (root->left == NULL && root->right == NULL)
allPath.push_back(currPath);
// traverse in the left subtree
treePathsSumUtil(root->left, currPath, allPath);
// traverse in the right subtree
treePathsSumUtil(root->right, currPath, allPath);
// remove the current element from the path
currPath.pop_back();
}
int treePathsSum(Node* root)
{
// store all the root to leaf path in allPath
vector<vector<string>> allPath;
vector<string> v;
treePathsSumUtil(root, v, allPath);
// store the sum
int s = 0;
for(auto pathNumber : allPath)
{
string k="";
// join the pathNumbers to convert them
// into the number to calculate sum
for(auto x: pathNumber)
k = k+x;
s += stoi(k);
}
return s;
}
// Driver code
int main()
{
Node *root = new Node(6);
root->left = new Node(3);
root->right = new Node(5);
root->left->left = new Node(2);
root->left->right = new Node(5);
root->right->right = new Node(4);
root->left->right->left = new Node(7);
root->left->right->right = new Node(4);
cout<<"Sum of all paths is "<<treePathsSum(root);
return 0;
}
// This code is contributed by Abhijeet Kumar(abhijeet19403)
Python3
# Python program to find sum of all paths from root to leaves
# A Binary tree node
class Node:
# Constructor to create a new node
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def treePathsSumUtil(root, currPath, allPath):
# Base Case
if root is None:
return
# append the root data in string format in currPath
currPath.append(str(root.data))
# if we found a leaf node we copy the the currPath to allPath
if root.left is None and root.right is None:
allPath.append(currPath.copy())
# traverse in the left subtree
treePathsSumUtil(root.left, currPath, allPath)
# traverse in the right subtree
treePathsSumUtil(root.right, currPath, allPath)
# remove the current element from the path
del currPath[-1]
def treePathsSum(root):
# store all the root to leaf path in allPath
allPath = []
treePathsSumUtil(root, [], allPath)
# store the sum
s = 0
for pathNumber in allPath:
# join the pathNumbers to convert them into the number to calculate sum
k = "".join(pathNumber)
s += int(k)
return s
# Driver function to test above function
root = Node(6)
root.left = Node(3)
root.right = Node(5)
root.left.left = Node(2)
root.left.right = Node(5)
root.right.right = Node(4)
root.left.right.left = Node(7)
root.left.right.right = Node(4)
print("Sum of all paths is", treePathsSum(root))
# this code is contributed by Vivek Maddeshiya
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