嘤嘤的新平衡树【牛客tracker 每日一题】
嘤嘤的新平衡树网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述给定一棵二叉树二叉树的每个结点只有0或2个孩子。你需要对每个结点赋值一个正整数使得每个结点的左右子树权值和相等。你需要返回所有结点的最小权值和对 10971097 取模的结果。二叉树结点个数不超过105105。示例1输入{0,0,0}返回值3解题思路本题要求在一棵每个内部节点都有两个孩子的二叉树中为每个节点分配正整数权值使得每个节点的左、右子树总权值和相等求所有节点权值之和的最小值。利用自底向上的归纳构造可以证明最小总权值只与树的高度有关答案为2 h − 1 2^{h} - 12h−1其中h hh为树的高度叶子高度为1 11。1. 问题分析平衡条件对于任意非叶节点u uu设其左子树的总权值为L LL右子树的总权值为R RR必须满足L R L RLR。节点u uu自身的权值w u ≥ 1 w_u \ge 1wu≥1可任意选择。总权值定义子树总权值为该子树内所有节点权值之和。目标最小化整棵树的总权值∑ w i \sum w_i∑wi对10 9 7 10^971097取模。2. 贪心构造与数学归纳采用自底向上的构造方法叶子节点高度h 1 h1h1没有孩子内部平衡条件自然满足。为最小化权值取权值1 11。子树总权值S ( 1 ) 1 2 1 − 1 S(1) 1 2^1 - 1S(1)121−1。内部节点假设左子树高度为h 1 h_1h1右子树高度为h 2 h_2h2。由归纳假设左子树可以构造出总权值为2 h 1 − 1 2^{h_1} - 12h1−1的合法方案右子树可以构造出2 h 2 − 1 2^{h_2} - 12h2−1的方案。为使左右子树的权值和相等不妨设h 1 ≥ h 2 h_1 \ge h_2h1≥h2。我们可以保持左子树不变总权值L 2 h 1 − 1 L 2^{h_1} - 1L2h1−1而将右子树的总权值提升至L LL。提升的方法很简单只需增加右子树内部某些节点的权值即可因为任何子树的总权值都可以在保持内部平衡的前提下任意增大例如增加根节点权值不影响子树的平衡性。因此右子树可以达到L LL。此时令左右相等值S L 2 h 1 − 1 S L 2^{h_1} - 1SL2h1−1再令当前节点的权值w u 1 w_u 1wu1最小值则以u uu为根的子树总权值为T L R 1 2 ( 2 h 1 − 1 ) 1 2 h 1 1 − 1. T L R 1 2(2^{h_1} - 1) 1 2^{h_11} - 1.TLR12(2h1−1)12h11−1.子树的高度为h max ( h 1 , h 2 ) 1 h 1 1 h \max(h_1, h_2) 1 h_1 1hmax(h1,h2)1h11故T 2 h − 1 T 2^h - 1T2h−1。由此归纳整棵树的最小总权值为2 H − 1 2^{H} - 12H−1其中H HH为树的高度。3. 算法实现求树的高度递归计算每个节点的高度。对于空节点返回0 00对于非空节点高度 max ( 左子树高度 , 右子树高度 ) 1 \max(左子树高度, 右子树高度) 1max(左子树高度,右子树高度)1。叶子节点左右皆空故高度为1 11。计算答案设整棵树高度为h hh使用快速幂计算2 h m o d ( 10 9 7 ) 2^h \bmod (10^97)2hmod(1097)然后减去1 11并处理模运算即可。4. 复杂度分析时间复杂度O ( n ) O(n)O(n)只需一次 DFS 遍历计算高度再一次快速幂O ( log h ) O(\log h)O(logh)。空间复杂度O ( n ) O(n)O(n)递归栈深度为树高。代码简要说明dfs(TreeNode* u)返回以u uu为根的子树高度。空树返回0 00否则返回左右子树高度的最大值加1 11。getTreeSum(TreeNode* tree)若树为空返回0 00否则计算高度h hh用快速幂qmi(2, h, mod)得到2 h m o d m o d 2^h \bmod mod2hmodmod返回( 2 h − 1 m o d ) m o d m o d (2^h - 1 mod) \bmod mod(2h−1mod)modmod。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;classSolution{public:llqmi(ll a,ll b,ll c){ll r1;while(b){if(b1)rr*a%c;aa*a%c;b1;}returnr;}lldfs(TreeNode*u){if(!u)return0;returnmax(dfs(u-left),dfs(u-right))1;}llgetTreeSum(TreeNode*tree){if(!tree)return0;ll hdfs(tree);return(qmi(2,h,mod)-1mod)%mod;}};
)
