给定一个二叉树。任务是编写一个程序来寻找给定二叉树所有节点的乘积。
在上面的二叉树中， 积= 15 * 10 * 8 * 12 * 20 * 16 * 25 = 115200000
想法是递归:
- 求左子树的积。
- 找到正确子树的乘积。
- 将左右子树的乘积与当前节点的数据相乘并返回。
以下是上述方法的实现:
c
// program to print product of all
// the nodes of a binary tree
#include
using namespace std;
// binary tree node
struct node {
int key;
node *left, *right;
};
/* utility that allocates a new node
with the given key */
node* newnode(int key)
{
node* node = new node;
node->key = key;
node->left = node->right = null;
return (node);
}
// function to find product of
// all the nodes
int productbt(node* root)
{
if (root == null)
return 1;
return (root->key * productbt(root->left) * productbt(root->right));
}
// driver code
int main()
{
// binary tree is:
// 1
// / \
// 2 3
// / \ / \
// 4 5 6 7
// \
// 8
node* root = newnode(1);
root->left = newnode(2);
root->right = newnode(3);
root->left->left = newnode(4);
root->left->right = newnode(5);
root->right->left = newnode(6);
root->right->right = newnode(7);
root->right->left->right = newnode(8);
int prod = productbt(root);
cout << "product of all the nodes is: "
<< prod << endl;
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java program to print product of all
// the nodes of a binary tree
import java.util.*;
class solution
{
// binary tree node
static class node {
int key;
node left, right;
};
/* utility that allocates a new node
with the given key */
static node newnode(int key)
{
node node = new node();
node.key = key;
node.left = node.right = null;
return (node);
}
// function to find product of
// all the nodes
static int productbt(node root)
{
if (root == null)
return 1;
return (root.key * productbt(root.left) * productbt(root.right));
}
// driver code
public static void main(string args[])
{
// binary tree is:
// 1
// / \
// 2 3
// / \ / \
// 4 5 6 7
// \
// 8
node root = newnode(1);
root.left = newnode(2);
root.right = newnode(3);
root.left.left = newnode(4);
root.left.right = newnode(5);
root.right.left = newnode(6);
root.right.right = newnode(7);
root.right.left.right = newnode(8);
int prod = productbt(root);
system.out.println( "product of all the nodes is: " prod);
}
}
//contributed by arnab kundu
python 3
# python3 program to print product of
# all the nodes of a binary tree
# binary tree node
""" utility that allocates a new node
with the given key """
class newnode:
# construct to create a new node
def __init__(self, key):
self.key = key
self.left = none
self.right = none
# function to find product of
# all the nodes
def productbt( root) :
if (root == none):
return 1
return (root.key * productbt(root.left) *
productbt(root.right))
# driver code
if __name__ == '__main__':
# binary tree is:
# 1
# / \
# 2 3
# / \ / \
# 4 5 6 7
# \
# 8
root = newnode(1)
root.left = newnode(2)
root.right = newnode(3)
root.left.left = newnode(4)
root.left.right = newnode(5)
root.right.left = newnode(6)
root.right.right = newnode(7)
root.right.left.right = newnode(8)
prod = productbt(root)
print("product of all the nodes is:", prod)
# this code is contributed by
# shubham singh(shubhamsingh10)
c
// c# program to print product of all
// the nodes of a binary tree
using system;
class gfg
{
// binary tree node
class node
{
public int key;
public node left, right;
};
/* utility that allocates a new node
with the given key */
static node newnode(int key)
{
node node = new node();
node.key = key;
node.left = node.right = null;
return (node);
}
// function to find product of
// all the nodes
static int productbt(node root)
{
if (root == null)
return 1;
return (root.key * productbt(root.left) *
productbt(root.right));
}
// driver code
public static void main()
{
// binary tree is:
// 1
// / \
// 2 3
// / \ / \
// 4 5 6 7
// \
// 8
node root = newnode(1);
root.left = newnode(2);
root.right = newnode(3);
root.left.left = newnode(4);
root.left.right = newnode(5);
root.right.left = newnode(6);
root.right.right = newnode(7);
root.right.left.right = newnode(8);
int prod = productbt(root);
console.writeline( "product of all "
"the nodes is: " prod);
}
}
/* this code is contributed princiraj1992 */
java 描述语言
java 描述语言
输出:
product of all the nodes is: 40320
时间复杂度: o(n)
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
