栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

LeetCode 662:二叉树最大宽度

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

LeetCode 662:二叉树最大宽度

二叉树最大宽度

题目:

思路:

利用把二叉树打印成多行的思路,将存节点的链表的size 用于分层 !
给每个节点一个位置position值,其左右子节点的位置分别为 position*2 和 position*2+1
新建一个CustomNode类存如TreeNode以及对应的position
每一层的宽度: width=最右position-最左position+1
每一层(即一个for循环)用一个ArrayList装position,for循环结束后计算当前层的width

Java实现:
class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        // 利用size分层
        // 每一轮用list装position
        Queue nodes=new LinkedList<>();
        int width=0;
        if(root!=null){
            nodes.add(new CustomNode(root,1)); // CustomNode需要new出来!
        }   
        while(!nodes.isEmpty()){
			// 每一层用list记录
            // 每一轮for弹出node
            // 每一次for用size分层
            ArrayList list=new ArrayList<>();
            int size=nodes.size();
            for(int i=0;i
                CustomNode n=nodes.poll();
                list.add(n.position);
                if(n.node.left!=null){
                    nodes.add(new CustomNode(n.node.left,n.position*2));
                }
                if(n.node.right!=null){
                    nodes.add(new CustomNode(n.node.right,n.position*2+1));
                }
            }
            // 每层结束算最大宽度
            width=Math.max(width, list.get(list.size()-1) - list.get(0)+1);
        }
        return width;
    }
}


    class CustomNode{
        TreeNode node;
        int position;
        public CustomNode(TreeNode node,int position){
            this.node=node;
            this.position=position;
        } 
    }

注意:
计算最右position 用的是list.get(list.size()-1), list存的是当前层的position,中间有null也会算上,而nodes存的是下一层的所有节点,nodes.size()是节点个数 ≠ 宽度

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/952865.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号