leetcode662. 二叉树最大宽度

leetcode662. 二叉树最大宽度

三月 14, 2020

leetcode662. 二叉树最大宽度

给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。

每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。

示例 1:
输入: 

     1
   /   \
  3     2
 / \     \  
5   3     9

输出: 4
解释: 最大值出现在树的第 3 层，宽度为 4 (5,3,null,9)。

示例 2:
输入: 

    1
   /  
  3    
 / \       
5   3

输出: 2
解释: 最大值出现在树的第 3 层，宽度为 2 (5,3)。

示例 3:
输入: 

    1
   / \
  3   2 
 /        
5

输出: 2
解释: 最大值出现在树的第 2 层，宽度为 2 (3,2)。

我的思路

层序遍历。当前节点的左节点记为 2i ,右节点为 2i+1，类似于数组的序号值。然后用list维护当前层的所有节点值，最后list的头结点和尾结点就是左右窗口的边界。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public int widthOfBinaryTree(TreeNode root) {
        if(root==null)return 0;
        LinkedList<Integer>list=new LinkedList<>();
        Queue<TreeNode>queue=new LinkedList<>();
        list.add(1);
        queue.add(root);
        int ans=1;
        while(!queue.isEmpty()){
            int count=queue.size();
            for(int i=0;i<count;i++){
                TreeNode first=queue.poll();
                int index=list.removeFirst();
                if(first.left!=null){
                    queue.add(first.left);
                    list.add(index*2);
                }
                if(first.right!=null){
                    queue.add(first.right);
                    list.add(index*2+1);
                }
                
            }
            if(list.size()>=1)
            ans=Math.max(ans,list.getLast()-list.getFirst()+1);
        }
        return ans;
    }

leetcode 35/100