- 0. Leetcode [2236. 判断根结点是否等于子结点之和](https://leetcode.cn/problems/root-equals-sum-of-children/)
- 分析与解答
- 1. Leetcode [面试题 04.10. 检查子树](https://leetcode.cn/problems/check-subtree-lcci/)
- 分析与解答
- 2. Leetcode [面试题 04.06. 后继者](https://leetcode.cn/problems/successor-lcci/)
- 分析与解答
- 3. Leetcode [1110. 删点成林](https://leetcode.cn/problems/delete-nodes-and-return-forest/)
- 分析与解答
- 总结
分析与解答给你一个 二叉树 的根结点 root，该二叉树由恰好 3 个结点组成：根结点、左子结点和右子结点。
如果根结点值等于两个子结点值之和，返回 true ，否则返回 false 。
干就完事儿了
class Solution {
public:
bool checkTree(TreeNode* root) {
return root->val == (root->left->val + root->right->val);
}
};
1. Leetcode 面试题 04.10. 检查子树
分析与解答检查子树。你有两棵非常大的二叉树：T1，有几万个节点；T2，有几万个节点。设计一个算法，判断 T2 是否为 T1 的子树。
如果 T1 有这么一个节点 n，其子树与 T2 一模一样，则 T2 为 T1 的子树，也就是说，从节点 n 处把树砍断，得到的树与 T2 完全相同。
注意：此题相对书上原题略有改动。
解法 1：
首先想到的解法是遍历两个树后，通过寻找
T
1
T1
T1 中的子串
T
2
T2
T2，确定
T
2
T2
T2 是否为子树：
class Solution {
public:
// 中序遍历树
vector searchTree(TreeNode* root) {
vector result;
if (root->left == nullptr && root->right == nullptr) {
result.push_back(root->val);
return result;
}
if (root->left) {
vector left = searchTree(root->left);
for (auto num: left) {
result.push_back(num);
}
}
result.push_back(root->val);
if (root->right) {
vector right = searchTree(root->right);
for (auto num: right) {
result.push_back(num);
}
}
return result;
}
bool checkSubTree(TreeNode* t1, TreeNode* t2) {
if (t2 == nullptr) {
return false;
}
vector t1R = searchTree(t1);
vector t2R = searchTree(t2);
if (t2R.size() > t1R.size()) {
return false;
}
// 寻找子串
for (int i = 0; i < t1R.size(); ++i) {
if (t1R[i] == t2R[0]) {
int sameNum(0);
for (int j = 0; j < t2R.size(); ++j) {
if (t2R[j] != t1R[i + j]) {
break;
}
sameNum++;
}
if (sameNum == t2R.size()) {
return true;
}
}
}
return false;
}
};
解法 2：哈希树
树也可以用哈希表示其唯一性。对每一个节点，计算以其为根节点的子树的哈希值，通过哈希值判断树
T
2
T2
T2 是否为树
T
1
T1
T1 的子树：
class Solution {
public:
void calcHash(TreeNode* root) {
if (root == nullptr) {
return;
}
calcHash(root->left);
calcHash(root->right);
// 通过树节点值，计算相应的哈希值
unsigned long long l = root->left? root->left->val: 1153470;
unsigned long long r = root->right? root->right->val: 531287;
root->val = (int) ((unsigned long long)root->val * 1196347 + l * 73451 + r);
}
bool find(TreeNode* t1, TreeNode* t2) {
if (t1 == nullptr) {
return false;
}
// 比较 哈希值 确定 t2 是否为 t1 的子树
return t1->val == t2->val || find(t1->left, t2) || find(t1->right, t2);
}
bool checkSubTree(TreeNode* t1, TreeNode* t2) {
calcHash(t1);
calcHash(t2);
if (t2 == nullptr) {
return true;
}
return find(t1, t2);
}
};
2. Leetcode 面试题 04.06. 后继者
分析与解答设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。
如果指定节点没有对应的“下一个”节点，则返回null。
解法 1：
首先想到的解法是遍历树后，在 vector 中寻找指定节点位置：
class Solution {
vector nodeSet;
public:
void searchTree(TreeNode* root, TreeNode* p) {
if (root == nullptr) {
return;
}
searchTree(root->left, p);
nodeSet.push_back(root);
searchTree(root->right, p);
}
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
searchTree(root, p);
// 寻找指定节点位置
for (int i = 0; i < nodeSet.size() - 1; ++i) {
if (nodeSet[i]->val == p->val) {
return nodeSet[i + 1];
}
}
return nullptr;
}
};
解法 2：标记查询
可以在搜索树时进行标记，若找到指定节点，则存储下一个要查找的节点，若无下一个节点，则返回空指针。
class Solution {
bool findP; // 标记是否找到指定节点
TreeNode* ret; // 后继节点存储位置
public:
void searchTree(TreeNode* root, TreeNode* p) {
if (root == nullptr) {
return;
}
// 查找左子树
searchTree(root->left, p);
// 若找到指定节点且未填入后继节点，则当前根节点为指定节点的后继节点
if (findP && ret == nullptr) {
ret = root;
}
// 找到指定节点，将标记置为 true
if (root->val == p->val) {
findP = true;
}
// 查找右子树
searchTree(root->right, p);
}
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
ret = nullptr;
findP = false;
searchTree(root, p);
return ret;
}
};
3. Leetcode 1110. 删点成林
分析与解答给出二叉树的根节点 root，树上每个节点都有一个不同的值。
如果节点值在 to_delete 中出现，我们就把该节点从树上删去，最后得到一个森林（一些不相交的树构成的集合）。
返回森林中的每棵树。你可以按任意顺序组织答案。
遍历树，若根节点在要删除的节点中，则将其子树加入结果向量；若左子树在要删除的节点中，则将根节点的左指针置为空；若右子树在要删除的节点中，则将根节点的右指针置为空：
class Solution {
vector result;
public:
void findTrees(TreeNode* root, vector& to_delete) {
if (root == nullptr) {
return;
}
// 若根节点为要删除的节点，则将其左右子树放入 result 中
auto it = find(to_delete.begin(), to_delete.end(), root->val);
if (it != to_delete.end()) {
if (root->left) {
result.push_back(root->left);
}
if (root->right) {
result.push_back(root->right);
}
// 根节点在结果集中，从结果集中删除
auto ite = find(result.begin(), result.end(), root);
if (ite != result.end()) {
result.erase(ite);
}
}
if (root->left) {
findTrees(root->left, to_delete);
// 若左子节点为要删除的节点，将根节点的左指针置为空
auto it = find(to_delete.begin(), to_delete.end(), root->left->val);
if (it != to_delete.end()) {
root->left = nullptr;
}
}
if (root->right) {
findTrees(root->right, to_delete);
// 若右子节点为要删除的节点，将根节点的右指针置为空
auto it = find(to_delete.begin(), to_delete.end(), root->right->val);
if (it != to_delete.end()) {
root->right = nullptr;
}
}
}
vector delNodes(TreeNode* root, vector& to_delete) {
auto it = find(to_delete.begin(), to_delete.end(), root->val);
if (it == to_delete.end()) {
result.push_back(root);
}
findTrees(root, to_delete);
return result;
}
};
总结
今日收获：哈希树与树的标记
