9.1 bilibili 后端第二题

 class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int maxValue (TreeNode root) {
        // write code here
     if(root == null) return 0;
      int mm = maxc(root);
     return mm;
    }
    public static int maxc(TreeNode root){
        int res =0;
        Deque<TreeNode> deque = new ArrayDeque<>();
        deque.add(root);
        while(!deque.isEmpty()){
            int num = deque.size();
            int sum = 0;
            int maxchazhi = 0;
            for(int i=0;i<num;i++){
                TreeNode node = deque.remove(); 
                sum +=node.val;
                if(node.left != null) {
                    deque.addLast(node.left);
                    maxchazhi = Math.max(maxchazhi,node.left.val-node.val);
                }
                if(node.right != null) {
                   deque.addLast(node.right); 
                   maxchazhi = Math.max(maxchazhi,node.right.val-node.val);
                }
                
               
            }
            sum += maxchazhi;
            res = Math.max(sum,res);
        }
        return res;
    }

二叉树每个节点都有一个权值
每一层权值为该层所有节点权值之和
有一次交换某节点和它父节点的机会,至多交换一次,最大权值那层权值是多少
定义同一深度的所有节点为一层
示例
{3,2,3,4}    输出 7

我计算每层权值sum+与子节点的最大差值,通过率只有36%



#bilibili笔试#
全部评论
多多有几场笔试啊?大佬,为什么我现在还在初筛
点赞 回复 分享
发布于 2022-09-07 09:31 四川
世另我,老哥我和你思路一样,也是每层权值sum+与子节点的最大差值,也是通过率36%!
2 回复 分享
发布于 2022-09-01 22:43 北京
遍历的时候同时计算出父节点-子节点的最大值以及子节点-父节点的最大值。然后把把每层的结果都保存一下,一次层序遍历后,max=Math.max(max, 子节点-父节点最大值+上一层的和),max= Math.max(max, 父节点-子节点最大值+本层和)
1 回复 分享
发布于 2022-09-01 23:09 陕西
只考虑了和向下的一层交换是这样的,向上和向下的都要考虑
1 回复 分享
发布于 2022-09-01 22:58 广东
从上往下遍历一遍,然后再从下往上遍历一遍嗷
点赞 回复 分享
发布于 2022-09-02 01:25 海南
父节点也可以被换下来
点赞 回复 分享
发布于 2022-09-02 00:33 北京

相关推荐

不愿透露姓名的神秘牛友
07-02 15:39
希望奇迹发生的布莱克...:真的是 现在卷实习就是没苦硬吃
点赞 评论 收藏
分享
代码飞升:别用口语,后端就写后端,前端就写前端,最后别光后悔
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 11:30
仁者伍敌:kpi都懒得刷了属于是
点赞 评论 收藏
分享
评论
4
2
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务