資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
廣告