当前位置：首页 > ops >正文

灵神题单之链表、树

ops 2025/9/5 5:30:15

链表系列

包含遍历，插删，反转，前后指针，快慢指针，双指针，合并链表等。

思考：

1、什么时候用哨兵节点？

答：当链表操作可能改变原始 head（比如插入/删除会在头部发生）或你希望把“头结点”与“非头结点”的处理统一成一套代码时，用 dummy。它能把很多头结点的特殊分支（if head == nullptr / 插入第一个节点 / 删除头结点）都消掉，代码更短、更安全、更不易出错。

典型场景

删除满足某个条件的节点（可能删除头节点），例如“删除链表中值为 x 的所有节点”。
删除第 n 个节点（尤其是从头部删除第 1 个节点）。
合并若干链表、按条件拆分链表或按节点值构造新链表（用 tail 指针不停 append）。
用双指针（快慢指针）删除倒数第 k 个节点时，常配合 dummy 以便统一返回 dummy->next 作为新头

2、while (node != null) 还是 while (node.next != null)？

答：取决于你在循环体内要访问/操作哪个节点（当前节点 node 还是下一个节点 node->next），以及循环的终止条件应该是到达“最后一个节点”还是“越过最后一个节点”。

2058.找出临界点之间的最小和最大距离

链表中的 临界点 定义为一个 局部极大值点 或 局部极小值点。

如果当前节点的值 严格大于 前一个节点和后一个节点，那么这个节点就是一个 局部极大值点 。

如果当前节点的值 严格小于 前一个节点和后一个节点，那么这个节点就是一个 局部极小值点 。

注意：节点只有在同时存在前一个节点和后一个节点的情况下，才能成为一个 局部极大值点 / 极小值点 。

给你一个链表 head ，返回一个长度为 2 的数组 [minDistance, maxDistance] ，其中 minDistance 是任意两个不同临界点之间的最小距离，maxDistance 是任意两个不同临界点之间的最大距离。如果临界点少于两个，则返回 [-1，-1]

注意审题，只是求任意临界点，并不是两个不同类型临界点。

class Solution {
public:vector<int> nodesBetweenCriticalPoints(ListNode* head) {int cnt = 0;vector<int> store; int pre;ListNode* q = head;ListNode* n;while (q != nullptr) {if (cnt == 0) {pre = q->val;cnt++;q = q->next;continue;}n = q->next;if (n == nullptr) break;if (pre < q->val && q->val > n->val) {store.push_back(cnt);pre = q->val;q = q->next;cnt++;} else if (pre > q->val && q->val < n->val) { store.push_back(cnt);pre = q->val;q = q->next;cnt++;} else {pre = q->val;q = q->next;cnt++;}}if (store.size() < 2) {return {-1, -1};}int minDistance = INT_MAX;int maxDistance = store.back() - store.front(); for (int i = 1; i < store.size(); i++) {int diff = store[i] - store[i - 1];if (diff < minDistance) {minDistance = diff;}}return {minDistance, maxDistance};}
};

817.链表组件

给定链表头结点 head，该链表上的每个结点都有一个 唯一的整型值 。同时给定列表 nums，该列表是上述链表中整型值的一个子集。

返回列表 nums 中组件的个数，这里对组件的定义为：链表中一段最长连续结点的值（该值必须在列表 nums 中）构成的集合。

傻逼题。地狱级的题意理解，不建议做。

class Solution {
public:int numComponents(ListNode* head, vector<int>& nums) {unordered_set<int> numsSet;for (int num : nums) {numsSet.emplace(num);}bool inSet = false;int res = 0;while (head != nullptr) {if (numsSet.count(head->val)) {if (!inSet) {inSet = true;res++;}} else {inSet = false;}head = head->next;}return res;}
};

237.删除链表中的节点

有一个单链表的 head，我们想删除它其中的一个节点 node。

给你一个需要删除的节点 node 。你将 无法访问 第一个节点 head。

链表的所有值都是 唯一的，并且保证给定的节点 node 不是链表中的最后一个节点。

删除给定的节点。注意，删除节点并不是指从内存中删除它。这里的意思是：

给定节点的值不应该存在于链表中。
链表中的节点数应该减少 1。
node 前面的所有值顺序相同。
node 后面的所有值顺序相同。

更是煞笔题。没给头结点的删除（也就无法通过遍历），变换一下思路。

class Solution {
public:void deleteNode(ListNode* node) {//把它与后一个调换，然后删后一个ListNode* n=node->next;int t=node->val;node->val=n->val;n->val=t;node->next=n->next;return ;}
};

2487.从链表中移除节点

给你一个链表的头节点 head 。

移除每个右侧有一个更大数值的节点。

返回修改后链表的头节点 head 。

灵神的思考很棒：

带着问题去做下面的题目：

在什么情况下，要用到哨兵节点（dummy node）？
在什么情况下，循环条件要写 while (node != null)？什么情况下要写 while (node.next != null)？

对于这题，需要删头结点，就要用到哨兵；此外，写完才发现这题似乎该用stack。

此外，注意写法！

ListNode dummy(0); 这是在栈上创建对象（所以用.访问）

ListNode* dummy = new ListNode(0); 这是创建指向 ListNode 的指针！实际对象是在堆上分配的

class Solution {
public:ListNode* removeNodes(ListNode* head) {deque<ListNode*> myque;ListNode* p = head;while (p != nullptr) {int value = p->val;while (!myque.empty() && myque.back()->val < value) {myque.pop_back();}myque.push_back(p);p = p->next;}ListNode dummy(0); ListNode* current = &dummy;for (ListNode* node : myque) {current->next = node;current = current->next;}current->next = nullptr;return dummy.next;}
};

LCR029.循环有序列表的插入

给定循环单调非递减列表中的一个点，写一个函数向这个列表中插入一个新元素 insertVal ，使这个列表仍然是循环升序的。

给定的可以是这个列表中任意一个顶点的指针，并不一定是这个列表中最小元素的指针。

如果有多个满足条件的插入位置，可以选择任意一个位置插入新的值，插入后整个列表仍然保持有序。

如果列表为空（给定的节点是 null），需要创建一个循环有序列表并返回这个节点。否则。请返回原先给定的节点。

注意边界条件：

class Solution {
public:Node* insert(Node* head, int insertVal) {if (head == nullptr) {Node* newNode = new Node(insertVal);newNode->next = newNode;return newNode;}Node* p = head;do {Node* q = p->next;// 情况1：正常区间 (p->val <= q->val)，且 insertVal 在 [p->val, q->val] 内if (p->val <= q->val) {if (p->val <= insertVal && insertVal <= q->val) {insertNode(p, q, insertVal);return head;}}// 情况2：下降点 (p->val > q->val)，且 insertVal >= p->val 或 <= q->valelse {if (insertVal >= p->val || insertVal <= q->val) {insertNode(p, q, insertVal);return head;}}p = q;} while (p != head);// 未插入（全等链表），插入在 head 之后insertNode(head, head->next, insertVal);return head;}private:void insertNode(Node* p, Node* q, int insertVal) {Node* newNode = new Node(insertVal);p->next = newNode;newNode->next = q;}
};

2074.反转偶数长度组的节点

给你一个链表的头节点 head 。

链表中的节点 按顺序 划分成若干非空组，这些非空组的长度构成一个自然数序列（1, 2, 3, 4, ...）。一个组的长度就是组中分配到的节点数目。换句话说：

节点 1 分配给第一组
节点 2 和 3 分配给第二组
节点 4、5 和 6 分配给第三组，以此类推

注意，最后一组的长度可能小于或者等于 1 + 倒数第二组的长度 。

反转每个偶数长度组中的节点，并返回修改后链表的头节点 head 。

本题数据量不大，链表最长才10^5，所以完全可以考虑使用数组的办法。此外，这里一个困难点事数组末尾的特判（可能最后长度不足但也为偶数），思路是老老实实写，前面也考虑奇数长度的情况（只不过不翻转），不用跳步。

class Solution {
public:ListNode* reverseEvenLengthGroups(ListNode* head) {vector<int>node;ListNode* p=head;while(p!=nullptr){node.push_back(p->val);p=p->next;}     int len=node.size();if(len<=2)return head;int cur=1;int k=2;while(cur<=len){if(len-cur<k&&(len-cur)%2==0){reverse(node.begin()+cur,node.end());break;}else if(len-cur>=k){if(k%2==0)reverse(node.begin()+cur,node.begin()+cur+k);}cur+=k;k++;}// for(int num:node)cout<<num<<" ";p=head;for(int i=1;i<len;i++){ListNode* q=new ListNode(node[i]);p->next=q;p=q;}return head;}
};

2130.链表最大孪生和

在一个大小为 n 且 n 为偶数的链表中，对于 0 <= i <= (n / 2) - 1 的 i ，第 i 个节点（下标从 0 开始）的孪生节点为第 (n-1-i) 个节点。

比方说，n = 4 那么节点 0 是节点 3 的孪生节点，节点 1 是节点 2 的孪生节点。这是长度为 n = 4 的链表中所有的孪生节点。

孪生和 定义为一个节点和它孪生节点两者值之和。

给你一个长度为偶数的链表的头节点 head ，请你返回链表的 最大孪生和

水题，如果用数组的话。感觉也只能用数组好

class Solution {
public:int pairSum(ListNode* head) {vector<int>store;ListNode* p=head;while(p!=nullptr){store.push_back(p->val);p=p->next;}int le=0;int ri=store.size()-1;int ans=-1;while(le<ri){ans=max(ans,store[le]+store[ri]);le++;ri--;}return ans;}
};

457.环形数组是否存在环

存在一个不含 0 的环形数组 nums ，每个 nums[i] 都表示位于下标 i 的角色应该向前或向后移动的下标个数：

如果 nums[i] 是正数，向前（下标递增方向）移动 |nums[i]| 步
如果 nums[i] 是负数，向后（下标递减方向）移动 |nums[i]| 步

因为数组是环形的，所以可以假设从最后一个元素向前移动一步会到达第一个元素，而第一个元素向后移动一步会到达最后一个元素。

数组中的循环由长度为 k 的下标序列 seq 标识：

遵循上述移动规则将导致一组重复下标序列 seq[0] -> seq[1] -> ... -> seq[k - 1] -> seq[0] -> ...
所有 nums[seq[j]] 应当不是全正就是全负
k > 1

如果 nums 中存在循环，返回 true ；否则，返回 false

很不错的题！注意一个点：关于负数的取模和正数的思维是一样的。此外，这里是判断循环，而不是判断环！！所以当再次到达起点时，需要判断方向！方向和前面的一样才是循环！

class Solution {
public:bool circularArrayLoop(vector<int>& nums) {unordered_set<int> death;int len = nums.size();if (len <= 1) return false;for (int i = 0; i < len; ++i) {nums[i] %= len; // C++ 对负数取余会得到负余数，范围 -(len-1) .. (len-1)if (nums[i] == 0) death.insert(i);}for (int i = 0; i < len; ++i) {if (death.count(i)) continue;unordered_set<int> temp;int cur = i;bool dir = nums[cur] > 0; while (true) {if (death.count(cur)) {for (int x : temp) death.insert(x);break;}if (temp.count(cur)) {int next = (cur + nums[cur]) % len;if (next < 0) next += len;if (next == cur) {for (int x : temp) death.insert(x);break;} else {return true;}}temp.insert(cur);int nxt = (cur + nums[cur]) % len;if (nxt < 0) nxt += len;// 如果下一步是已标死亡或者方向不同，则当前路径无效，全部标死亡并停止if (death.count(nxt) || nums[nxt] == 0 || ((nums[nxt] > 0) != dir)) {for (int x : temp) death.insert(x);break;}cur = nxt;} // end while} // end forreturn false;}
};

143.重排链表

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换

也是很好的题：

每次先把左边节点的 next 指到右端，再把右端的 next 指到下一个左端。循环结束后 i 即为尾结点索引，把 store[i]->next = nullptr 即可

class Solution {
public:void reorderList(ListNode* head) {if (!head || !head->next) return;vector<ListNode*> store;ListNode* p = head;while (p) {store.push_back(p);p = p->next;}int i = 0, j = (int)store.size() - 1;while (i < j) {store[i]->next = store[j];++i;if (i == j) break;store[j]->next = store[i];--j;}// 最后把尾结点 next 置空store[i]->next = nullptr;}
};

不过，GPT给出了相当优质的解法！结合了快慢指针+链表合并，非常值得学习！

class Solution {
public:void reorderList(ListNode* head) {if (!head || !head->next) return;// 1. 找中点（快慢指针）ListNode *slow = head, *fast = head;while (fast->next && fast->next->next) {slow = slow->next;fast = fast->next->next;}// slow 为中点（前半段末尾）ListNode* second = slow->next;slow->next = nullptr; // 切断前半段// 2. 反转后半段ListNode* prev = nullptr;while (second) {ListNode* nxt = second->next;second->next = prev;prev = second;second = nxt;}// prev 是反转后半段的头// 3. 合并两段ListNode *p1 = head, *p2 = prev;while (p2) {ListNode* t1 = p1->next;ListNode* t2 = p2->next;p1->next = p2;p2->next = t1;p1 = t1;p2 = t2;}}
};

328.奇偶链表

给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别分组，保持它们原有的相对顺序，然后把偶数索引节点分组连接到奇数索引节点分组之后，返回重新排序的链表。

第一个节点的索引被认为是奇数， 第二个节点的索引为偶数，以此类推。

请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。

你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。

经典的双指针问题！很不错

class Solution {
public:ListNode* oddEvenList(ListNode* head) {ListNode* dummy1=new ListNode(0);ListNode* dummy2=new ListNode(0);ListNode* slow=dummy1;ListNode* fast=dummy2;ListNode* p=head; while(p!=nullptr){slow->next=p;slow=slow->next;if(p->next!=nullptr){fast->next=p->next;fast=fast->next;p=p->next->next;}else break;}fast->next=nullptr;slow->next=dummy2->next;return dummy1->next;}
};

445.两数相加2

给你两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头

留个心眼，这里看数据很显然是要套高精加的。

此外，注意前导0的处理（细节），只有当 ret.size() > 1 时才去除末尾的零！（不然结果为0全抹去了）

class Solution {
public:vector<int>count(vector<int>&a,vector<int>&b){reverse(a.begin(),a.end());reverse(b.begin(),b.end());vector<int>ret;int len1=a.size();int len2=b.size();int t=0;for(int i=0;i<len2;i++){int num=(a[i]+b[i]+t)%10;ret.push_back(num);t=(a[i]+b[i]+t)/10;}for(int i=len2;i<len1;i++){int num=(a[i]+t)%10;ret.push_back(num);t=(a[i]+t)/10;}while(t!=0){ret.push_back(t%10);t/=10;}while(ret.back()==0&&ret.size()>1)ret.pop_back();return ret;}ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* p=l1;vector<int>a,b;while(p!=nullptr){a.push_back(p->val);p=p->next;}p=l2;while(p!=nullptr){b.push_back(p->val);p=p->next;}vector<int>c;if(a.size()>=b.size())c=count(a,b);else c=count(b,a);reverse(c.begin(),c.end());int len=c.size();ListNode* dummy=new ListNode(0);ListNode* pre=dummy;for(int i=0;i<len;i++){ListNode* p=new ListNode(c[i]);pre->next=p;pre=p;}return dummy->next;}
};

2816.翻倍以链表形式表示的数字

给你一个非空链表的头节点 head ，表示一个不含前导零的非负数整数。

将链表翻倍后，返回头节点 head 。

和上面一样，只不过换成了乘法。

class Solution {
public:vector<int>count(vector<int>&a){reverse(a.begin(),a.end());int len=a.size();int t=0;vector<int>ret;for(int i=0;i<len;i++){ret.push_back((a[i]*2+t)%10);t=(a[i]*2+t)/10;}while(t!=0){ret.push_back(t%10);t/=10;}while(ret.back()==0&&ret.size()>1)ret.pop_back();return ret;}ListNode* doubleIt(ListNode* head) {vector<int>a;ListNode* p=head;while(p!=nullptr){a.push_back(p->val);p=p->next;}vector<int>c=count(a);reverse(c.begin(),c.end());ListNode* dummy=new ListNode(0);p=dummy;int len=c.size();for(int i=0;i<len;i++){ListNode* q=new ListNode(c[i]);p->next=q;p=q;}return dummy->next;}
};

二叉树系列

思考：

1、一般，DFS 的递归边界是空节点。在什么情况下，要额外把叶子节点作为递归边界？

递归的最自然边界是空节点 node == nullptr，因为这保证你不会再往下访问子指针；空节点作为“没有更多信息”的返回点，配合父节点去组合左右子结果（例如计算高度、节点数）最方便。

对于某些边界值在空节点处不好返回，需要特殊处理单子树情形，需要把叶子节点做递归边界，比如根到叶子路径和计算最小深度 所以在写递归前应优先判断用哪个递归条件

2、DFS 什么时候需要返回值？

当子问题的结果需要被父节点使用或合并时，递归就应该有返回值。具体而言，两类：合并左右子树的信息来算当前节点的值和父节点需要根据子树结果做决策或剪枝

3、什么时候用自顶向下什么时候用自底向上？

这个问题也应该在写之前就明晰！

如果答案依赖「父或路径上已累积的状态」——用自顶向下。
如果答案依赖「子节点的聚合信息来构造当前节点的答案」——用自底向上

671.二叉树中第二小的节点

给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么该节点的值等于两个子节点中较小的一个。

更正式地说，即 root.val = min(root.left.val, root.right.val) 总成立。

给出这样的一个二叉树，你需要输出所有节点中的 第二小的值 。

如果第二小的值不存在的话，输出 -1 。

节点的取值可达2^31-1

本题我用set来做的，显然需要用long long，注意最大值是LLONG_MAX！

class Solution {
public:using ll=long long;unordered_set<ll>mset;void dfs(TreeNode* root){if(root==nullptr)return ;dfs(root->left);mset.insert(root->val);dfs(root->right);return ;}int findSecondMinimumValue(TreeNode* root) {if(root==nullptr)return -1;dfs(root);ll themin=LLONG_MAX;for(ll num:mset){if(num<themin)themin=min(themin,num);}mset.erase(themin);if(mset.empty())return -1;themin=LLONG_MAX;for(ll num:mset){if(num<themin)themin=min(themin,num);}return (int)themin;}
};

我感觉二叉树的遍历这一类题似乎都可以通过用vector存节点值来做。。。（因为树不会很大）

1026.节点与其祖先之间的最大差值

给定二叉树的根节点 root，找出存在于不同节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。

（如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）

树的dfs遍历除了基础版以外往往需要维护某些值，比如这里就是祖先的最值（维护的目的其实就是为了维护A是B的祖先这个条件）

class Solution {
public:int ans=-1;void dfs1(TreeNode* root,int curmin,int curmax){if(root==nullptr)return ;curmin=min(curmin,root->val);curmax=max(curmax,root->val);ans=max(ans,curmax-curmin);dfs1(root->left,curmin,curmax);dfs1(root->right,curmin,curmax);return ;}int maxAncestorDiff(TreeNode* root) {dfs1(root,INT_MAX,-1);return ans;}
};

1022.从根到叶的二进制数之和

给出一棵二叉树，其上每个结点的值都是 0 或 1 。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。

例如，如果路径为 0 -> 1 -> 1 -> 0 -> 1，那么它表示二进制数 01101，也就是 13 。

对树上的每一片叶子，我们都要找出从根到该叶子的路径所表示的数字。

返回这些数字之和。题目数据保证答案是一个 32 位 整数。

强调一个点：不要在root=null时加，这样把空节点也当成叶子节点！实际空节点不参与运算

值应该只在叶子结点加！

class Solution {
public:int ans = 0;void dfs(TreeNode* root, int cur) {if (!root) return;cur = (cur << 1) | root->val;  if (!root->left && !root->right) {ans += cur;  // 只在叶子节点累加return;}dfs(root->left, cur);dfs(root->right, cur);}int sumRootToLeaf(TreeNode* root) {dfs(root, 0);return ans;}
};

插播：集合的遍历除了可用迭代器也可以像数组一样：

for (int n : nums)

1372.二叉树中的最长交错路径

给你一棵以 root 为根的二叉树，二叉树中的交错路径定义如下：

选择二叉树中任意节点和一个方向（左或者右）。
如果前进方向为右，那么移动到当前节点的的右子节点，否则移动到它的左子节点。
改变前进方向：左变右或者右变左。
重复第二步和第三步，直到你在树中无法继续移动。

交错路径的长度定义为：访问过的节点数目 - 1（单个节点的路径长度为 0 ）。

请你返回给定树中最长 交错路径 的长度。

自顶向下的DFS（先序遍历），灵神的总结同样精辟：在「递」的过程中维护值

这里考虑到数据量，搜索过程需要加入记忆化。

class Solution {
public:int ans=0;vector<TreeNode*>store;unordered_map<TreeNode*,vector<int>>mmap;int dfs(TreeNode* root,int book){if(mmap.find(root)!=mmap.end()){for(int num:mmap[root]){if(book*num>0)return abs(num);}}if(root==nullptr){return -1;}int a=0;if(book==1){a=dfs(root->left,book*-1);}else if(book==-1){a=dfs(root->right,book*-1);}int cur=a+1;ans=max(ans,cur);mmap[root].push_back(cur*book);return cur;}void dfs2(TreeNode* root){if(root==nullptr)return;dfs2(root->left);dfs2(root->right);store.push_back(root);return ;}int longestZigZag(TreeNode* root) {dfs2(root);for(auto k:store){dfs(k,1);dfs(k,-1);}return ans;}
};

不用记忆化，GPT给出了通俗的做法：非常值得学习

pair<int,int> dfs(TreeNode* node) {if (!node) return {-1, -1}; // 使用 -1 作为空节点的基础，这样 leaf 的 child 返回 -1，leaf 的 left = (-1)+1 = 0（单边长度为0）auto L = dfs(node->left);auto R = dfs(node->right);int leftFirst = L.second + 1;   // 先向左，下一步应该在左子节点处向右，所以用 L.secondint rightFirst = R.first + 1;   // 先向右，下一步应该在右子节点处向左，所以用 R.firstans = max(ans, max(leftFirst, rightFirst));return {leftFirst, rightFirst};}

2265.统计值等于子树平均值的节点数

给你一棵二叉树的根节点 root ，找出并返回满足要求的节点数，要求节点的值等于其子树中值的 平均值 。

注意：

n 个元素的平均值可以由 n 个元素求和然后再除以 n ，并 向下舍入 到最近的整数。
root 的子树由 root 和它的所有后代组成。

这是非常经典的自底向上DFS（后序遍历），灵神的总结是：在「归」的过程中计算！

（其实就是分析题意，看要求的东西是在什么时候求，进而决定用什么遍历方式）

class Solution {
public:using pii=pair<int,int>;int ans=0;pii dfs(TreeNode* root){if(root==nullptr)return make_pair(0,0);auto [a,num1]=dfs(root->left);auto [b,num2]=dfs(root->right);int c=a+b+root->val;int d=num1+num2+1;if(c/d==root->val)ans++;return make_pair(c,d);}int averageOfSubtree(TreeNode* root) {dfs(root);return ans;}
};

3319.第k大的完美二叉子树的大小

给你一棵 二叉树 的根节点 root 和一个整数k。

返回第 k 大的 完美二叉子树的大小，如果不存在则返回 -1。

完美二叉树 是指所有叶子节点都在同一层级的树，且每个父节点恰有两个子节点。

完美二叉树需要子树的height相同且均为完美——》引入一个struct为宜（注意struct的使用！）

此外，本题同样是自底向上的DFS，非常不错的题。

class Solution {
public:struct Info{bool perfect;int height;int num;};vector<int>store;Info dfs(TreeNode* root){if(root==nullptr)return {true,0,0};Info l=dfs(root->left);Info r=dfs(root->right);if(l.perfect&&r.perfect&&l.height==r.height){store.push_back(l.num+r.num+1);return {true,l.height+1,l.num+r.num+1};}else{Info cur;cur.perfect=false;cur.height=max(l.height,r.height)+1;cur.num=l.num+r.num+1;return cur;}}int kthLargestPerfectSubtree(TreeNode* root, int k) {dfs(root);if(k>store.size())return -1;sort(store.begin(),store.end(),greater<int>());return store[k-1];}
};

1145.二叉树着色游戏

有两位极客玩家参与了一场「二叉树着色」的游戏。游戏中，给出二叉树的根节点 root，树上总共有 n 个节点，且 n 为奇数，其中每个节点上的值从 1 到 n 各不相同。

最开始时：

「一号」玩家从 [1, n] 中取一个值 x（1 <= x <= n）；
「二号」玩家也从 [1, n] 中取一个值 y（1 <= y <= n）且 y != x。

「一号」玩家给值为 x 的节点染上红色，而「二号」玩家给值为 y 的节点染上蓝色。

之后两位玩家轮流进行操作，「一号」玩家先手。每一回合，玩家选择一个被他染过色的节点，将所选节点一个 未着色 的邻节点（即左右子节点、或父节点）进行染色（「一号」玩家染红色，「二号」玩家染蓝色）。

如果（且仅在此种情况下）当前玩家无法找到这样的节点来染色时，其回合就会被跳过。

若两个玩家都没有可以染色的节点时，游戏结束。着色节点最多的那位玩家获得胜利 ✌️。

现在，假设你是「二号」玩家，根据所给出的输入，假如存在一个 y 值可以确保你赢得这场游戏，则返回 true ；若无法获胜，就请返回 false 。

非常有意思的题，核心在于分析，用别人精辟的话概括是：当红色方先手后，蓝色方有三个区域可以下棋，分别是x的左右子树和父节点，有一个区域大于总节点数的一半就可以了

同样是自底向上的后序。

class Solution {
public:int area1=0;int area2=0;int dfs(TreeNode* root,int x){if(root==nullptr)return 0;int a=dfs(root->left,x);int b=dfs(root->right,x);if(root->val==x){area1=a;area2=b;}return a+b+1;}bool btreeGameWinningMove(TreeNode* root, int n, int x) {dfs(root,x);int t=max(max(area1,area2),(n-area1-area2-1));cout<<area1<<" "<<area2;if(2*t>=n)return true;return false;}
};

LCP67.装饰树

力扣嘉年华上的 DIY 手工展位准备了一棵缩小版的二叉装饰树 root 和灯饰，你需要将灯饰逐一插入装饰树中，要求如下：

完成装饰的二叉树根结点与 root 的根结点值相同
若一个节点拥有父节点，则在该节点和他的父节点之间插入一个灯饰（即插入一个值为 -1 的节点）。具体地：
- 在一个父节点 x 与其左子节点 y 之间添加 -1 节点，节点 -1、节点 y 为各自父节点的左子节点，
- 在一个父节点 x 与其右子节点 y 之间添加 -1 节点，节点 -1、节点 y 为各自父节点的右子节点，

现给定二叉树的根节点 root ，请返回完成装饰后的树的根节点

同样是自底向上，归的时候插入

class Solution {
public:void dfs(TreeNode* root){if(root==nullptr)return;dfs(root->left);dfs(root->right);if(root->left){TreeNode* p=new TreeNode(-1);p->left=root->left;root->left=p;}if(root->right){TreeNode* p=new TreeNode(-1);p->right=root->right;root->right=p;}return ;}TreeNode* expandBinaryTree(TreeNode* root) {dfs(root);return root;}
};

1110.删点成林

给出二叉树的根节点 root，树上每个节点都有一个不同的值。

如果节点值在 to_delete 中出现，我们就把该节点从树上删去，最后得到一个森林（一些不相交的树构成的集合）。

返回森林中的每棵树。你可以按任意顺序组织答案

强调一个点，这个点经常犯错：只是把 root = nullptr; 并不能从父节点把指针切断——这是在本地修改了局部指针，不会影响父节点指针（换而言之，父节点还是指向含数据的地方）

所以dfs需要返回值，来更新父节点的指向。

class Solution {
public:vector<TreeNode*> res;unordered_set<int> delSet;TreeNode* dfs(TreeNode* node) {if (!node) return nullptr;node->left = dfs(node->left);node->right = dfs(node->right);if (delSet.count(node->val)) {if (node->left) res.push_back(node->left);if (node->right) res.push_back(node->right);return nullptr; }return node;}vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {res.clear();delSet.clear();for (int v : to_delete) delSet.insert(v);TreeNode* newRoot = dfs(root);if (newRoot) res.push_back(newRoot); return res;}
};