662. 二叉树最大宽度

662. 二叉树最大宽度

难度中等530

给你一棵二叉树的根节点 root 返回树的 最大宽度 。

树的 最大宽度 是所有层中最大的 宽度 。

每一层的 宽度 被定义为该层最左和最右的非空节点即两个端点之间的长度。将这个二叉树视作与满二叉树结构相同两端点间会出现一些延伸到这一层的 null 节点这些 null 节点也计入长度。

题目数据保证答案将会在  32 位 带符号整数范围内。

示例 1

输入root = [1,3,2,5,3,null,9]
输出4
解释最大宽度出现在树的第 3 层宽度为 4 (5,3,null,9) 。

示例 2

输入root = [1,3,2,5,null,null,9,6,null,7]
输出7
解释最大宽度出现在树的第 4 层宽度为 7 (6,null,null,null,null,null,7) 。

示例 3

输入root = [1,3,2,5]
输出2
解释最大宽度出现在树的第 2 层宽度为 2 (3,2) 。

提示

• 树中节点的数目范围是 [1, 3000]
• -100 <= Node.val <= 100

思路

• 进行层序遍历,使用index给每一个节点进行编号,对于一个节点编号为index,那么左子树节点编号为2*index,右子树节点编号为2*index+1;
• 每遍历一层都需要结算当前层的最大宽度,我们可以在遍历每一层的开始之前先记录一个initindex,然后在定义一个变量index,用于给每一个节点进行编号,那么当每一层遍历完成之后,index就是当前层的最后节点的编号,那么最大宽度就是 index-initIndex +1
• 遍历每一层取最大,返回maxi即可

 

迭代

• 使用两个队列,一个队列存放二叉树的节点,一个队列存放二叉树节点的编号
• 每遍历一层的开始之前要记录initindex,作为每一层的起始编号,在使用index给节点编号,左子树节点编号为2*index,右子树节点编号为2*index+1
• 遍历完一层,index就是这一层的最后一个节点编号
• 最大宽度为index-initindex+1,遍历二叉树的每一层取最大即可

class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();//一个队列存放二叉树的节点
        Queue<Integer> queueIndex = new LinkedList<>();//一个队列存放二叉树节点的编号
        queue.offer(root);
        queueIndex.offer(1);
        int maxi = 0;
        while(!queue.isEmpty()) {
            int sz = queue.size();//记录当前遍历层节点个数
            int initIndex = queueIndex.peek();//作为每一层的起始编号
            int index = initIndex;//使用index给节点编号,遍历完一层,index就是这一层的最后一个节点编号
            for(int i =0;i<sz;++i) {//一层一层遍历
                TreeNode cur = queue.poll();
                index = queueIndex.poll();
                if(cur.left!=null) {
                    queue.offer(cur.left);
                    queueIndex.offer(2*index);
                }
                if(cur.right!=null) {
                    queue.offer(cur.right);
                    queueIndex.offer(2*index+1);
                }
            }
            //最大宽度为index-initindex+1,遍历二叉树的每一层取最大即可
            maxi = Math.max(maxi,(index-initIndex)+1);
        }
        return maxi;
    }
}

递归

• 每一层节点开始的时候记录index,表示每一层节点其实编号,也就是用res存放在每一层起始节点编号
• 递归遍历,取最大宽度即可,参考上面思路都是一样的,难点就是用res存放在每一层起始节点编号

class Solution {   
    private int maxi = 0;
    private void dfs(TreeNode root,int index,int level,List<Integer> res) {
        if(root==null) return;
        if(level==res.size()) {
            res.add(index);
        }
        maxi = Math.max(maxi,(index - res.get(level)) + 1);
        dfs(root.left,2*index,level+1,res);
        dfs(root.right,2*index+1,level+1,res);
    }
    public int widthOfBinaryTree(TreeNode root) {
        if(root==null) return 0;
        dfs(root,1,0,new ArrayList<>());
        return maxi;
    }
}