数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 C++ 中查找给定二叉树中所有右叶子的和
在这个问题中，我们给定一个二叉树。我们的任务是找到给定二叉树中所有右叶子的和。
让我们举一个例子来理解这个问题，
输入
输出：8
解释 -
All leaf nodes of the tree are : 1, 8 Sum = 1 + 8 = 9
解决方案方法
解决此问题的一个简单方案是从根节点到叶子节点遍历树。如果一个节点是左叶子节点，则将其添加到总和中。遍历完整棵树后。打印总和。
示例
程序说明我们解决方案的工作原理
#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 findRightLeavesSum(Node *root){
int sum = 0;
if (root != NULL){
if (isLeafNode(root->right))
sum += root->right->key;
else
sum += findRightLeavesSum(root->right);
sum += findRightLeavesSum(root->left);
}
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 right leaves of the tree is "<<findRightLeavesSum(root);
return 0;
}输出
The sum of right leaves of the tree is 8
另一种使用迭代的方法
我们将对树执行深度优先搜索遍历，然后检查当前节点是否为右叶子。如果是，则将其值添加到总和中，否则跳过。最后，打印总和。
示例
程序说明我们解决方案的工作原理
#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 findRightLeavesSum(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->right != NULL){
treeNodes.push(currentNode->right);
if(currentNode->right->right == NULL &&
currentNode->right->left == NULL){
sum += currentNode->right->key ;
}
}
if (currentNode->left != NULL)
treeNodes.push(currentNode->left);
}
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 right leaves of the tree is "<<findRightLeavesSum(root);
return 0;
}输出
The sum of right leaves of the tree is 8
方法 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 findRightLeavesSum(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, 0 });
}
if (temp->right) {
leftTreeNodes.push({ temp->right, 1 });
}
}
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 right leaves of the tree is "<<findRightLeavesSum(root);
return 0;
}输出
The sum of right leaves of the tree is 8
更新于：2022年1月25日
344 次浏览
广告