LeetCode 1430. Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree
原题链接
中等
作者:
JasonSun
,
2020-08-27 14:17:49
,
所有人可见
,
阅读 367
Tree Fold with Accumulator
class Solution {
public:
bool isValidSequence(TreeNode* root, vector<int>& arr) {
const int N = std::size(arr);
auto is_leaf = [&](TreeNode* n) { return n->left == nullptr and n->right == nullptr; };
const auto solution = [&](bool self = false) {
std::function<void(TreeNode*, int)> fold = [&](TreeNode* n, int level) {
if (n == nullptr or self == true) {
return;
}
else {
self |= is_leaf(n) and (level == N - 1 and n->val == arr[N - 1]);
if (level < N and n->val == arr[level]) {
fold(n->left, level + 1);
fold(n->right, level + 1);
}
}
};
return fold(root, 0), self;
}();
return solution;
}
};
Tree Fold with Backtracking
class Solution {
public:
bool isValidSequence(TreeNode* root, vector<int>& arr) {
const auto solution = [&](bool self = false) {
std::function<void(TreeNode*)> fold = [&, acc = std::vector<int>{}](TreeNode* n) mutable {
if (n == nullptr or self == true) {
return;
}
else if (n->left == nullptr and n->right == nullptr) {
acc.emplace_back(n->val);
if (acc == arr) {
std::exchange(self, true);
return;
}
acc.pop_back();
}
else {
if (n->left) {
acc.emplace_back(n->val);
fold(n->left);
acc.pop_back();
}
if (n->right) {
acc.emplace_back(n->val);
fold(n->right);
acc.pop_back();
}
}
};
return fold(root), self;
}();
return solution;
}
};