首页 > itarticle > [leetcode] problem 662 – maximum width of binary tree

[leetcode] problem 662 – maximum width of binary tree

admin 11月 13, 2020 0

Given a binary tree, write a function to get the maximum width of the given tree. The width of a tree is the maximum width among all levels. The binary tree has the same structure as a full binary tree, but some nodes are null.

The width of one level is defined as the length between the end-nodes (the leftmost and right most non-null nodes in the level, where the null nodes between the end-nodes are also counted into the length calculation.

Example

No.1

Input: 

1
2
3
4
5
 
     1
   /   
  3     2
 /        
5   3     9

Output: 4

Explanation: The maximum width existing in the third level with the length 4 (5,3,null,9).

No.2

Input: 

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
28
29
30
31
32
33
34
35
36
37
38
39
 
          1
         /  
        3    
       /        
      5   3    
``` 

Output: 2

Explanation: The maximum width existing in the third level with the length 2 (5,3).



Input: 

```bash
          1
         / 
        3   2 
       /        
      5   
```   

Output: 2

Explanation: The maximum width existing in the second level with the length 2 (3,2).

### No.4

Input: 

```bash
          1
         / 
        3   2
       /       
      5       9 
     /         
    6           7

Output: 8

Explanation:The maximum width existing in the fourth level with the length 8 (6,null,null,null,null,null,null,7).

Note

Answer will in the range of 32-bit signed integer.

Code

1
2
3
4
5
6
 
public class  {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
 
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
28
29
30
 
public int widthOfBinaryTree(TreeNode root) {
    if (root == null)
        return 0;

    int max = 0;
    LinkedList<TreeNode> queue = new LinkedList<>();
    root.val = 0;
    queue.offer(root);

    while (!queue.isEmpty()) {
        int size = queue.size();
        max = Math.max(max, queue.peekLast().val - queue.peekFirst().val + 1);

        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();

            if (node.left != null) {
                node.left.val = node.val * 2;
                queue.offer(node.left);
            }

            if (node.right != null) {
                node.right.val = node.val * 2 + 1;
                queue.offer(node.right);
            }
        }
    }

    return max;
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能