資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中查詢給定二叉樹中所有左葉子的和
在這個問題中，我們給定一個二叉樹。我們的任務是查詢給定二叉樹中所有左葉子的和。
讓我們舉一個例子來理解這個問題，
輸入：
輸出：11
解釋 -
All leaf nodes of the tree are : 2, 9 Sum = 2 + 9 = 11
解決方案方法
解決此問題的一個簡單方法是從根到葉遍歷樹。如果一個節點是左葉子節點，則將其新增到總和中。當遍歷整個樹時。列印總和。
示例
程式說明我們解決方案的工作原理
#include <iostream>
using namespace std;
struct Node{
int key;
struct Node* left, *right;
};
Node *newNode(char k){
Node *node = new Node;
node->key = k;
node->right = node->left = NULL;
return node;
}
bool isLeafNode(Node *node){
if (node == NULL)
return false;
if (node->left == NULL && node->right == NULL)
return true;
return false;
}
int findLeftLeavesSum(Node *root){
int sum = 0;
if (root != NULL){
if (isLeafNode(root->left))
sum += root->left->key;
else
sum += findLeftLeavesSum(root->left);
sum += findLeftLeavesSum(root->right);
}
return sum;
}
int main(){
struct Node *root = newNode(5);
root->left = newNode(4);
root->right = newNode(6);
root->left->left = newNode(2);
root->left->right = newNode(1);
root->right->left = newNode(9);
root->right->right = newNode(7);
cout<<"The sum of left leaves of the tree is "<<findLeftLeavesSum(root);
return 0;
}輸出
The sum of left leaves of the tree is 11
另一種使用迭代的方法
我們將對樹執行深度優先搜尋遍歷，然後檢查當前節點是否為左葉子。如果是，則將其值新增到總和中，否則，離開。最後，列印總和。
示例
程式說明我們解決方案的工作原理
#include<bits/stdc++.h>
using namespace std;
struct Node{
int key;
struct Node* left, *right;
};
Node *newNode(char k){
Node *node = new Node;
node->key = k;
node->right = node->left = NULL;
return node;
}
int findLeftLeavesSum(Node* root){
if(root == NULL)
return 0;
stack<Node*> treeNodes;
treeNodes.push(root);
int sum = 0;
while(treeNodes.size() > 0){
Node* currentNode = treeNodes.top();
treeNodes.pop();
if (currentNode->left != NULL){
treeNodes.push(currentNode->left);
if(currentNode->left->left == NULL &&
currentNode->left->right == NULL){
sum += currentNode->left->key ;
}
}
if (currentNode->right != NULL)
treeNodes.push(currentNode->right);
}
return sum;
}
int main(){
Node *root = newNode(5);
root->left= newNode(4);
root->right = newNode(6);
root->left->left = newNode(2);
root->left->right = newNode(1);
root->right->left = newNode(9);
root->right->right= newNode(7);
cout<<"The sum of left leaves of the tree is "<<findLeftLeavesSum(root);
return 0;
}輸出
The sum of left leaves of the tree is 11
方法 3，使用 BFS
我們將執行廣度優先搜尋，並使用一個變數來指示節點是否是左子節點。如果是，則將其新增到總和中，否則，離開。最後，列印總和。
示例
程式說明我們解決方案的工作原理
#include<bits/stdc++.h>
using namespace std;
struct Node{
int key; struct Node* left, *right;
};
Node *newNode(char k){
Node *node = new Node;
node->key = k;
node->right = node->left = NULL;
return node;
}
int findLeftLeavesSum(Node* root) {
if (root == NULL)
return 0;
queue<pair<Node*, bool> > leftTreeNodes;
leftTreeNodes.push({ root, 0 });
int sum = 0;
while (!leftTreeNodes.empty()) {
Node* temp = leftTreeNodes.front().first;
bool is_left_child = leftTreeNodes.front().second;
leftTreeNodes.pop();
if (!temp->left && !temp->right && is_left_child)
sum = sum + temp->key;
if (temp->left) {
leftTreeNodes.push({ temp->left, 1 });
}
if (temp->right) {
leftTreeNodes.push({ temp->right, 0 });
}
}
return sum;
}
int main(){
Node *root = newNode(5);
root->left= newNode(4);
root->right = newNode(6);
root->left->left = newNode(2);
root->left->right = newNode(1);
root->right->left = newNode(9);
root->right->right= newNode(7);
cout<<"The sum of left leaves of the tree is "<<findLeftLeavesSum(root);
return 0;
}輸出
The sum of left leaves of the tree is 11
更新於：2022-01-25
332 次檢視
廣告