[數(shù)據(jù)結(jié)構(gòu)+算法] 給一棵樹(shù)和一個(gè)sum，判斷是否存在從root到葉子結(jié)點(diǎn)的path之和等于sum？

可以使用兩種方法求解

• 遞歸 CheckTreeSumRecursive

問(wèn)題轉(zhuǎn)換為遞歸判斷左右子樹(shù)是否滿(mǎn)足路徑和等于sum減去當(dāng)前節(jié)點(diǎn)的值。

• 迭代 CheckTreeSumNonRecursive

使用兩個(gè)棧數(shù)據(jù)結(jié)構(gòu)，一個(gè)存儲(chǔ)節(jié)點(diǎn)，另一個(gè)存儲(chǔ)對(duì)應(yīng)的節(jié)點(diǎn)到root節(jié)點(diǎn)到sum，迭代遍歷到葉子節(jié)點(diǎn)時(shí)進(jìn)行判斷。

詳細(xì)代碼如下：

#include <iostream>
#include <stack>using namespace std;struct TreeNode {TreeNode(int val_) : val(val_), left(nullptr), right(nullptr) {}int val;TreeNode *left;TreeNode *right;
};bool CheckTreeSumRecursive(TreeNode *head, int targetSum) {if (head == nullptr) {return false;}if (head->left == nullptr && head->right == nullptr && head->val == targetSum) {return true;}return CheckTreeSumRecursive(head->left, targetSum - head->val) || CheckTreeSumRecursive(head->right, targetSum - head->val);
}bool CheckTreeSumNonRecursive(TreeNode *head, int targetSum) {if (head == nullptr) {return false;}stack<TreeNode*> nodes;nodes.push(head);stack<int> sums;sums.push(head->val);while (!nodes.empty()) {TreeNode *node = nodes.top();nodes.pop();int sum = sums.top();sums.pop();if (node->left == nullptr && node->right == nullptr && sum == targetSum) {return true;}if (node->left != nullptr) {nodes.push(node->left);sums.push(sum + node->val);}if (node->right != nullptr) {nodes.push(node->right);sums.push(sum + node->val);}}return false;
}// 打印結(jié)果的輔助函數(shù)
void printResult(bool result) {cout << (result ? "true" : "false") << endl;
}int main() {// 創(chuàng)建示例二叉樹(shù)TreeNode* root = new TreeNode(5);root->left = new TreeNode(4);root->right = new TreeNode(8);root->left->left = new TreeNode(11);root->left->left->left = new TreeNode(7);root->left->left->right = new TreeNode(2);root->right->left = new TreeNode(13);root->right->right = new TreeNode(4);root->right->right->right = new TreeNode(1);cout << "Test Recursive Solution...\n";cout << "Example 1: ";printResult(CheckTreeSumRecursive(root, 22)); // 輸出 truecout << "Example 2: ";printResult(CheckTreeSumRecursive(root, 5)); // 輸出 falsecout << "Example 3: ";printResult(CheckTreeSumRecursive(nullptr, 0)); // 輸出 falsecout << "Test Recursive Solution...\n";cout << "Example 1: ";printResult(CheckTreeSumNonRecursive(root, 22)); // 輸出 truecout << "Example 2: ";printResult(CheckTreeSumNonRecursive(root, 5)); // 輸出 falsecout << "Example 3: ";printResult(CheckTreeSumNonRecursive(nullptr, 0)); // 輸出 falsereturn 0;
}