数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 C++ 中查找二叉树根节点到叶子节点路径中是否存在一对节点，其和等于根节点的值
在这个问题中，我们给定一棵二叉树。我们需要查找根节点到叶子节点路径中是否存在一对节点，其和等于根节点的值。
我们需要检查是否存在一对节点位于根节点到叶子节点的路径之间，使得这对节点的值之和等于根节点的值。
让我们举个例子来理解这个问题，
输入
输出：是
解释：
根节点值为 7
和等于根节点值的节点对：(2, 5), (1, 6)。
解决方案：
我们需要遍历树并使用哈希表查找节点对。
为此，我们将创建一个哈希表并遍历树。将数据插入哈希表，然后检查它与其他元素的和是否等于根节点的值。
最后，如果我们没有找到任何节点对，则返回false。
如果找到节点对，则返回true。
程序演示了我们解决方案的工作原理，
示例
#include<bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* left, *right;
};
struct Node* newnode(int data) {
struct Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
bool findSumUntill(Node *node, unordered_set<int> &hashTable, int rootVal)
{
if (node == NULL)
return false;
int otherVal = rootVal - node->data;
if (hashTable.find(otherVal) != hashTable.end())
return true;
hashTable.insert(node->data);
bool isFound = findSumUntill(node->left, hashTable, rootVal) || findSumUntill(node->right, hashTable, rootVal);
hashTable.erase(node->data);
return isFound;
}
bool findPairSum(Node *root) {
unordered_set<int> hashTable;
return findSumUntill(root->left, hashTable, root->data) || findSumUntill(root->right, hashTable, root->data);
}
int main()
{
struct Node *root = newnode(7);
root->left = newnode(2);
root->right = newnode(3);
root->left->left = newnode(5);
root->left->right = newnode(9);
root->left->left->left = newnode(1);
root->left->left->right = newnode(6);
root->right->left = newnode(8);
if(findPairSum(root))
cout<<"Pair with sum equal to root value found";
else
cout<<"No pairs found";
return 0;
}输出
Pair with sum equal to root value found
更新于： 2021年1月22日
73 次浏览
广告