子树和(subtree sum)
组别:提高组
难度:6
“子树和”通常指的是一棵树中某个子树的所有节点值的总和。对于一棵树，子树和的计算是树形结构中的一个常见操作，尤其是在处理诸如二叉树、n叉树等结构时。
要计算子树和，你通常需要遍历树的节点，并对每个节点的值进行累加。递归方法通常用于这种遍历，例如：
- 递归遍历：从某个节点开始，递归地访问其子节点，并将所有节点的值累加起来。这种方法适用于各种树形结构，包括二叉树和多叉树。
- 动态规划：在树的结构中，动态规划可以用于减少重复计算，特别是在需要对同一子树进行多次计算的情况下。你可以将每个子树的和存储在一个数组中，避免重复计算。
代码一：递归遍历
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | /**************************************************************** * Description: 子树和 递归 * Author: Alex Li * Date: 2024-08-13 13:11:07 * LastEditTime: 2024-08-13 13:11:18 ****************************************************************/ #include <iostream> using namespace std; struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; int subtreeSum(TreeNode* root) { if (root == nullptr) { return 0; // 空节点的和为0 } // 递归计算左子树和右子树的和 int leftSum = subtreeSum(root->left); int rightSum = subtreeSum(root->right); // 当前节点的子树和为：左子树和 + 右子树和 + 当前节点值 int totalSum = leftSum + rightSum + root->val; return totalSum; } int main() { // 示例树结构 TreeNode* root = new TreeNode(1); root->left = new TreeNode(2); root->right = new TreeNode(3); root->left->left = new TreeNode(4); root->left->right = new TreeNode(5); // 计算并输出根节点的子树和 cout << "子树和: " << subtreeSum(root) << endl; // 输出应该是15 return 0; } |
代码二：动态规划
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | /**************************************************************** * Description: 子树和 动态规划 * Author: Alex Li * Date: 2024-08-13 13:13:06 * LastEditTime: 2024-08-13 13:24:00 ****************************************************************/ #include <iostream> #include <unordered_map> using namespace std; struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; // 缓存子树和的哈希表 unordered_map<TreeNode*, int> subtreeSumCache; int subtreeSum(TreeNode* root) { if (root == nullptr) { return 0; // 空节点的和为0 } // 如果这个节点的子树和已经计算过了，就直接返回缓存值 if (subtreeSumCache.find(root) != subtreeSumCache.end()) { return subtreeSumCache[root]; } // 递归计算左子树和右子树的和 int leftSum = subtreeSum(root->left); int rightSum = subtreeSum(root->right); // 当前节点的子树和为：左子树和 + 右子树和 + 当前节点值 int totalSum = leftSum + rightSum + root->val; // 将计算结果存入缓存 subtreeSumCache[root] = totalSum; return totalSum; } int main() { // 示例树结构 TreeNode* root = new TreeNode(1); root->left = new TreeNode(2); root->right = new TreeNode(3); root->left->left = new TreeNode(4); root->left->right = new TreeNode(5); // 计算并输出根节点的子树和 cout << "子树和: " << subtreeSum(root) << endl; // 输出应该是15 return 0; } |