二叉树分裂问题常见操作：
-
将某个或某些子树单独取出
-
删除某个结点，使二叉树分裂成三部分（左子树，右子树，其它部分）
整体与局部
通常我们自底向上，找到需要处理的结点
这时我们天然地拥有以当前结点为根的子树的信息
如果我们提前预处理出整棵树的信息
并且我们需要研究的性质满足区间可加性，我们就可以直接算出其余部分的信息
例题1
leetcode 1339
题意
给你一棵二叉树，它的根为 root
请你删除 1 条边，使二叉树分裂成两棵子树，且它们子树和的乘积尽可能大
由于答案可能会很大，请你将结果对 10^9 + 7 取模后再返回
思路
1，预处理出整棵树的和
2，枚举要删除的结点，更新答案
code
你会发现dfs1与dfs2完全一样，后者只是多了一个答案更新而已
事实上完全可以调用两次dfs2,省略dfs1
不过为了清晰，我选择分开实现
class Solution {long long sum;long long ans;
public:int maxProduct(TreeNode* root) {this->ans=0;this->sum=dfs1(root);dfs2(root);return ans%1000000007;}long long dfs1(TreeNode*root){if(root==nullptr)return 0;long long l=dfs1(root->left);long long r=dfs1(root->right);return l+r+root->val;}long long dfs2(TreeNode*root){if(root==nullptr)return 0;long long l=dfs2(root->left);long long r=dfs2(root->right);long long cur=l+r+root->val;ans=max(ans,cur*(sum-cur));return cur;}
};
例题2
leetcode 1145
直接说思路
一号玩家在X处染色，将整棵树分成三部分
二号玩家若想必胜，需：
-
三个区域选择一个，贴着X染色
-
此区域结点数 > n/2 r( n=整棵树的结点数)
这样就将问题转化为：
求由 X 分裂出的三个部分中的最大值
code
class Solution {TreeNode*X;int x;
public:bool btreeGameWinningMove(TreeNode* root, int n, int x) {this->x=x;find(root);int b=dfs(X->left);int c=dfs(X->right);int a=dfs(root)-b-c-1;int m=max({a,b,c});if(m>n/2)return 1;return 0;}void find(TreeNode*root){if(root==nullptr)return;if(root->val==x){X=root;return;}find(root->left);find(root->right);}int dfs(TreeNode*root){if(root==nullptr)return 0;return 1+dfs(root->left)+dfs(root->right);}
};
例题3
leetcode 2049
与前面的题目大差不差，注意一下哈希的用法,分裂产生子树的数目可能是1、2、3
记得开long long
class Solution {long long n;vector<vector<int>>gra;unordered_map<long long,int>cnt;
public:int countHighestScoreNodes(vector<int>& parents) {this->n=parents.size();this->gra.resize(n);for(int i=1;i<n;i++){gra[parents[i]].push_back(i);}dfs(0);long long M=0;int ans;for(auto &[x,y]:cnt){if(M<x){M=x;ans=y;}}return ans;}long long dfs(int cur){long long sum=1;long long score=1;for(int x:gra[cur]){long long t=dfs(x);sum+=t;score*=max(1LL,t);}score*=max(1LL,n-sum);cnt[score]++;return sum;}
};