資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝學
法學在 C++ 中查詢同一層級葉子節點資料和的乘積
概念
對於給定的二叉樹，返回以下值。
對於每一層，如果該層存在葉子節點，則計算所有葉子節點的和。否則忽略。
計算所有層級和的乘積並返回。
輸入
Root of following tree 3 / \ 8 6 \ 10
輸出
80
第一層沒有葉子節點。第二層有一個葉子節點 8，第三層也有一個葉子節點 10。所以結果是 8 * 10 = 80
輸入
Root of following tree 3 / \ 8 6 / \ \ 9 7 10 / \ / \ 2 12 5 11
輸出
270
前兩層沒有葉子節點。第三層有一個葉子節點 9。最後一層有四個葉子節點 2、12、5 和 11。所以結果是 9 * (2 + 12 + 5 + 11) = 270
方法
對於一個簡單的解決方案，我們遞迴地計算從上到下所有層的葉子節點和。之後，將具有葉子節點的層的和相乘。此解決方案的時間複雜度為 O(n^2)。
對於一個高效的解決方案，我們實現基於佇列的層序遍歷。在此遍歷過程中，我們分別處理所有不同的層級。對於每個處理的層級，驗證它是否包含葉子節點。如果是，則計算葉子節點的和。最後，返回所有和的乘積。
示例
/* Iterative C++ program to find sum of data of all leaves
of a binary tree on same level and then multiply sums
obtained of all levels. */
#include <bits/stdc++.h>
using namespace std;
// Shows a Binary Tree Node
struct Node1 {
int data1;
struct Node1 *left1, *right1;
};
// Shows helper function to check if a Node is leaf of tree
bool isLeaf(Node1* root1){
return (!root1->left1 && !root1->right1);
}
/* Compute sum of all leaf Nodes at each level and returns
multiplication of sums */
int sumAndMultiplyLevelData(Node1* root1){
// Here tree is empty
if (!root1)
return 0;
int mul1 = 1; /* Used To store result */
// Build an empty queue for level order tarversal
queue<Node1*> q1;
// Used to Enqueue Root and initialize height
q1.push(root1);
// Perform level order traversal of tree
while (1) {
// NodeCount1 (queue size) indicates number of Nodes
// at current lelvel.
int NodeCount1 = q1.size();
// Now if there are no Nodes at current level, we are done
if (NodeCount1 == 0)
break;
// Used to initialize leaf sum for current level
int levelSum1 = 0;
// Shows a boolean variable to indicate if found a leaf
// Node at current level or not
bool leafFound1 = false;
// Used to Dequeue all Nodes of current level and Enqueue
all
// Nodes of next level
while (NodeCount1 > 0) {
// Process next Node of current level
Node1* Node1 = q1.front();
/* Now if Node is a leaf, update sum at the level */
if (isLeaf(Node1)) {
leafFound1 = true;
levelSum1 += Node1->data1;
}
q1.pop();
// Add children of Node
if (Node1->left1 != NULL)
q1.push(Node1->left1);
if (Node1->right1 != NULL)
q1.push(Node1->right1);
NodeCount1--;
}
// Now if we found at least one leaf, we multiply
// result with level sum.
if (leafFound1)
mul1 *= levelSum1;
}
return mul1; // Here, return result
}
//Shows utility function to create a new tree Node
Node1* newNode(int data1){
Node1* temp1 = new Node1;
temp1->data1 = data1;
temp1->left1 = temp1->right1 = NULL;
return temp1;
}
// Driver program to test above functions
int main(){
Node1* root1 = newNode(3);
root1->left1 = newNode(8);
root1->right1 = newNode(6);
root1->left1->right1 = newNode(7);
root1->left1->left1 = newNode(9);
root1->left1->right1->left1 = newNode(2);
root1->left1->right1->right1 = newNode(12);
root1->right1->right1 = newNode(10);
root1->right1->right1->left1 = newNode(5);
root1->right1->right1->right1 = newNode(11);
cout << "Final product value = "
<< sumAndMultiplyLevelData(root1) <<endl;
return 0;
}輸出
Final product value = 270
更新於：2020年7月25日
102 次瀏覽
廣告