网站建设与维护课程标准二级域名著名网站

[数据结构+算法] 给一棵树和一个sum，判断是否存在从root到叶子结点的path之和等于sum？

可以使用两种方法求解

• 递归 CheckTreeSumRecursive

问题转换为递归判断左右子树是否满足路径和等于sum减去当前节点的值。

• 迭代 CheckTreeSumNonRecursive

使用两个栈数据结构，一个存储节点，另一个存储对应的节点到root节点到sum，迭代遍历到叶子节点时进行判断。

详细代码如下：

#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;
}// 打印结果的辅助函数
void printResult(bool result) {cout << (result ? "true" : "false") << endl;
}int main() {// 创建示例二叉树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;
}