题目：https://leetcode.cn/problems/insufficient-nodes-in-root-to-leaf-paths/
好题，有递有归，有始有终！
过程如下：
- 前序时累加当前节点结果
- 到达叶子节点进行计算，标记符合要求的节点
- 后序时去掉当前节点结果
- 一个节点后续时表示已经走完所有的子节点，所以此时可以直接把不符合要求的左右子节点删掉
容易理解的回溯写法
class Solution {
public:
// 记录路径节点键值和
int nodeValueSum = 0;
// 记录路径节点
vector<TreeNode*> nodeSave;
// 每走完一条路径，标记符合要求的节点
set<TreeNode*> nodeMark;
void dfs(TreeNode* root, const int& limit) {
if (!root) {
return;
}
nodeValueSum += root->val;
nodeSave.push_back(root);
// 处理叶子节点
if (!root->left && !root->right) {
// 把当前路径上符合要求的标记
if (nodeValueSum >= limit) {
for (int i = 0; i < nodeSave.size(); ++i) {
nodeMark.insert(nodeSave[i]);
}
}
}
dfs(root->left, limit);
dfs(root->right, limit);
nodeValueSum -= root->val;
nodeSave.pop_back();
// 当前已经处理完这个节点的所有子节点，把没有标记过的，也就是不符合要求的删掉
if (!nodeMark.count(root->left)) root->left = nullptr;
if (!nodeMark.count(root->right)) root->right = nullptr;
}
TreeNode* sufficientSubset(TreeNode* root, int limit) {
dfs(root, limit);
return nodeMark.count(root) ? root : nullptr;
}
};
更好的写法
- 通过“递” sumValue，省掉上面的全局变量 nodeValueSum
- 通过“归” return bool，省掉上面的全局变量 nodeMark、nodeSave
class Solution {
public:
bool dfs(TreeNode* root, int sumValue, const int& limit) {
if (!root) return false;
// 处理叶子节点
if (!root->left && !root->right) return sumValue + root->val >= limit;
bool left = dfs(root->left, sumValue + root->val, limit);
bool right = dfs(root->right, sumValue + root->val, limit);
// 当前已经处理完这个节点的所有子节点，把没有标记过的，也就是不符合要求的删掉
if (!left) root->left = nullptr;
if (!right) root->right = nullptr;
return left || right;
}
TreeNode* sufficientSubset(TreeNode* root, int limit) {
return dfs(root, 0, limit) ? root : nullptr;
}
};