TODO：
树哈希还没看...
117. 填充每个节点的下一个右侧节点指针 II(中等)
只想到了层序，但是不满足空间复杂度为常数级别
方法一 层序遍历(空间复杂度不满足)
class Solution {
public:
Node* connect(Node* root) {
if(!root) return nullptr;
queue<Node*> Q;
Q.push(root);
while(!Q.empty()){
int qs = Q.size();
for(int i = 0; i < qs; i++){
Node* t = Q.front();
Q.pop();
if(t->left) Q.push(t->left);
if(t->right) Q.push(t->right);
Node* q = Q.front();
t->next = q;
if(i == qs-1) t->next = nullptr;
}
}
return root;
}
};
方法二
就很巧妙。在遍历了第一层后。
class Solution {
public:
Node* connect(Node* root) {
// if (root == null)
// return root;
//cur我们可以把它看做是每一层的链表
Node* cur = root;
while (cur != nullptr) {
//遍历当前层的时候，为了方便操作在下一
//层前面添加一个哑结点（注意这里是访问
//当前层的节点，然后把下一层的节点串起来）
Node* dummy = new Node(0);
//pre表示访下一层节点的前一个节点
Node* pre = dummy;
//然后开始遍历当前层的链表
while (cur != nullptr) {
if (cur->left != nullptr) {
//如果当前节点的左子节点不为空，就让pre节点
//的next指向他，也就是把它串起来
pre->next = cur->left;
//然后再更新pre
pre = pre->next;
}
//同理参照左子树
if (cur->right != nullptr) {
pre->next = cur->right;
pre = pre->next;
}
//继续访问这一行的下一个节点
cur = cur->next;
}
//把下一层串联成一个链表之后，让他赋值给cur，
//后续继续循环，直到cur为空为止
cur = dummy->next;
}
return root;
}
};
class Solution {
public:
void handle(Node* &last, Node* &p, Node* &nextStart) {
if (last) {
last->next = p;
}
if (!nextStart) {
nextStart = p;
}
last = p;
}
Node* connect(Node* root) {
if (!root) {
return nullptr;
}
Node *start = root;
while (start) {
Node *last = nullptr, *nextStart = nullptr;
for (Node *p = start; p != nullptr; p = p->next) {
if (p->left) {
handle(last, p->left, nextStart);
}
if (p->right) {
handle(last, p->right, nextStart);
}
}
start = nextStart;
}
return root;
}
};
572. 另一个树的子树(简单)
没做出来。
方法一 暴力递归
一个树是另一个树的子树 则
- 要么这两个树相等
- 要么这个树是左树的子树
- 要么这个树hi右树的子树
class Solution {
public:
bool isSame(TreeNode* root, TreeNode* subRoot){
if(root== nullptr && subRoot == nullptr) return true;
return root&&subRoot&&root->val == subRoot->val && isSame(root->left,subRoot->left) && isSame(root->right,subRoot->right);
}
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
if(!root) return subRoot == nullptr;
// if(!subRoot) return root == nullptr;
return isSame(root,subRoot) || isSubtree(root->left,subRoot) ||isSubtree(root->right,subRoot);
}
};
方法二 深度优先序列上做串匹配
class Solution {
public:
vector <int> sOrder, tOrder;
int maxElement, lNull, rNull;
void getMaxElement(TreeNode *o) {//算出最大值以将其设置为空
if (!o) {
return;
}
maxElement = max(maxElement, o->val);
getMaxElement(o->left);
getMaxElement(o->right);
}
void getDfsOrder(TreeNode *o, vector <int> &tar) { //序列化
if (!o) {
return;
}
tar.push_back(o->val);
if (o->left) {
getDfsOrder(o->left, tar);
} else {
tar.push_back(lNull);
}
if (o->right) {
getDfsOrder(o->right, tar);
} else {
tar.push_back(rNull);
}
}
bool kmp() {
int sLen = sOrder.size(), tLen = tOrder.size();
vector <int> fail(tOrder.size(), -1);
for(int i = 1, j =-1; i < tLen; ++i){
while(j != -1 && tOrder[i]!=tOrder[j+1]){
j = fail[j];
}
if(tOrder[i] == tOrder[j+1]){
++j;
}
fail[i] = j;
}
for(int i = 0, j =-1; i < sLen; ++i){
while(j!=-1 && sOrder[i]!=tOrder[j+1]){
j = fail[j];
}
if(sOrder[i] == tOrder[j+1]){
j++;
}
if( j == tLen-1) return true;
}
return false;
}
bool isSubtree(TreeNode* s, TreeNode* t) {
maxElement = INT_MIN;
getMaxElement(s);
getMaxElement(t);
lNull = maxElement + 1;
rNull = maxElement + 2;
getDfsOrder(s, sOrder);
getDfsOrder(t, tOrder);
return kmp();
}
};
方法三 树哈希
完全没看明白呢，下次遇到了再学吧。
题解
class Solution {
public:
static constexpr int MAX_N = 1000 + 5;
static constexpr int MOD = int(1E9) + 7;
bool vis[MAX_N];
int p[MAX_N], tot;
void getPrime() {
vis[0] = vis[1] = 1; tot = 0;
for (int i = 2; i < MAX_N; ++i) {
if (!vis[i]) p[++tot] = i;
for (int j = 1; j <= tot && i * p[j] < MAX_N; ++j) {
vis[i * p[j]] = 1;
if (i % p[j] == 0) break;
}
}
}
struct Status {
int f, s; // f 为哈希值 | s 为子树大小
Status(int f_ = 0, int s_ = 0)
: f(f_), s(s_) {}
};
unordered_map <TreeNode *, Status> hS, hT;
void dfs(TreeNode *o, unordered_map <TreeNode *, Status> &h) {
h[o] = Status(o->val, 1);
if (!o->left && !o->right) return;
if (o->left) {
dfs(o->left, h);
h[o].s += h[o->left].s;
h[o].f = (h[o].f + (31LL * h[o->left].f * p[h[o->left].s]) % MOD) % MOD;
}
if (o->right) {
dfs(o->right, h);
h[o].s += h[o->right].s;
h[o].f = (h[o].f + (179LL * h[o->right].f * p[h[o->right].s]) % MOD) % MOD;
}
}
bool isSubtree(TreeNode* s, TreeNode* t) {
getPrime();
dfs(s, hS);
dfs(t, hT);
int tHash = hT[t].f;
for (const auto &[k, v]: hS) {
if (v.f == tHash) {
return true;
}
}
return false;
}
};
