662. Maximum Width of Binary Tree

发表于 | 分类于 | |

662. Maximum Width of Binary Tree

题目描述

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.

1
2
3
4
5
6
7
8
9
10
11
Example 1:
Input: 
           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).
1
2
3
4
5
6
7
8
9
10
11
Example 2:
Input: 
          1
         /  
        3    
       / \       
      5   3     
Output: 2
Explanation: The maximum width existing in the third level with the length 2 (5,3).
1
2
3
4
5
6
7
8
9
10
11
Example 3:
Input: 
          1
         / \
        3   2 
       /        
      5      
Output: 2
Explanation: The maximum width existing in the second level with the length 2 (3,2).
1
2
3
4
5
6
7
8
9
10
11
12
Example 4:
Input: 
          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).

题目大意

给定一个二叉树，求每层最左节点到最右节点距离的最大值。

解题思路

层序遍历，辅助队列，左节点的个数则为：i 2,右节点的个数则为：i 2 + 1
队列的首元素和末元素的差值 + 1即为宽度。
刚开始用的Int，但是会越界，于是改用Double.

代码

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */
class Solution {
    func widthOfBinaryTree(_ root: TreeNode?) -> Int {
        guard let root = root else { return 0 }
        var queue = [(0.0, root)]
        var ans = 0.0
        while !queue.isEmpty {
            let width = queue.last!.0 - queue.first!.0 + 1
            ans = max(ans, width)
            
            var tmp = [(Double, TreeNode)]()
            for (i, node) in queue {
                if let left = node.left { tmp.append((i * 2.0, left)) }
                if let right = node.right { tmp.append((i * 2.0 + 1.0, right)) }
            }
            queue = tmp
        }
        return Int(ans)
    }
}
0%