[Swift]LeetCode662.二叉树最大宽度|MaximumWidthofBinaryTree

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10492131.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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 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).

Example 2:

Input: 

          1
         /  
        3    
       / \       
      5   3     

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

Example 3:

Input: 

          1
         / \
        3   2 
       /        
      5      

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

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).

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

给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（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)。

示例 4:

输入: 

          1
         / \
        3   2
       /     \  
      5       9 
     /         \
    6           7
输出: 8
解释: 最大值出现在树的第 4 层，宽度为 8 (6,null,null,null,null,null,null,7)。

注意: 答案在32位有符号整数的表示范围内。

Runtime: 20 ms

Memory Usage: 19.4 MB

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15      func widthOfBinaryTree(_ root: TreeNode?) -> Int {
16         guard let root = root else { return 0 }
17         var queue: [(TreeNode, Int)] = []
18         queue.append((root, 1))
19         var maxLen = 1
20         while !queue.isEmpty {
21             let count = queue.count
22             for _ in 0 ..< count {
23                 let curr = queue.removeFirst() 
24                 let index = curr.1
25                 if let left = curr.0.left {
26                     queue.append((left, index &* 2))
27                 }
28 
29                 if let right = curr.0.right {
30                     queue.append((right, index &* 2 + 1))
31                 }
32             }
33             if !queue.isEmpty {
34                 maxLen = max(maxLen, queue.last!.1 &- queue.first!.1 &+ 1)                
35             }
36         }
37         
38         return maxLen
39     }
40 }

20ms

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     func widthOfBinaryTree(_ root: TreeNode?) -> Int {
16         guard let root = root else { return 0 }
17         var lastLevel = -1, startIdx = 0
18         var result = 1
19         var queue = [(node: root, level: 0, idx: 0)]
20         while queue.count > 0 {
21             let (node, level, idx) = queue.removeFirst()
22             if lastLevel != level {
23                 startIdx = idx
24                 lastLevel = level
25             } else {
26                 result = max(result, idx - startIdx + 1)
27             }
28             
29             if let left = node.left {
30                 queue.append((left, level + 1, (idx - startIdx) * 2 + 1))
31             }
32             if let right = node.right {
33                 queue.append((right, level + 1, (idx - startIdx) * 2 + 2))
34             }
35         }
36         return result
37     }
38 }

28ms

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     
16     func widthOfBinaryTree(_ root: TreeNode?) -> Int {
17         guard let root = root else { return 0 }
18         var nodes: [(Int, TreeNode)] = [(0, root)]
19         var maxWidth = 1
20         while !nodes.isEmpty {
21             var nextNodes: [(Int, TreeNode)] = []
22             var index = 0
23             var lastNodeIndex = -1
24             for (nodeIndex, node) in nodes {
25                 if lastNodeIndex >= 0 {
26                     index += (nodeIndex - lastNodeIndex - 1) * 2
27                 }
28                 lastNodeIndex = nodeIndex
29                 if let left = node.left {
30                     nextNodes.append((index, left))
31                 }
32                 index += 1
33                 if let right = node.right {
34                     nextNodes.append((index, right))
35                 }
36                 index += 1
37             }
38             nodes = nextNodes
39             if let firstIndex = nodes.first?.0, let lastIndex = nodes.last?.0 {
40                 maxWidth = max(maxWidth, lastIndex - firstIndex + 1)
41             }
42         }
43         return maxWidth
44     }
45 }

32ms

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     func widthOfBinaryTree(_ root: TreeNode?) -> Int {
16         guard let root = root else {
17             return 0
18         }
19         
20         var queue = [(TreeNode, Int)]()
21         var maxWidth = 1
22         
23         queue.append((root, 0))
24         while !queue.isEmpty {
25             let count = queue.count
26             let firstNode = queue.first!
27             let lastNode = queue.last!
28             maxWidth = max(maxWidth, lastNode.1 - firstNode.1 + 1)
29             for _ in 0..<count {
30                 let (node, val) = queue.removeFirst()
31                 if let leftNode = node.left {
32                     queue.append((leftNode, val * 2 - 1))
33                 }
34                 if let rightNode = node.right {
35                     queue.append((rightNode, val * 2))
36                 }
37             }
38         }
39         
40         return maxWidth
41     }
42 }

40ms

  1 /**
  2  * Definition for a binary tree node.
  3  * public class TreeNode {
  4  *     public var val: Int
  5  *     public var left: TreeNode?
  6  *     public var right: TreeNode?
  7  *     public init(_ val: Int) {
  8  *         self.val = val
  9  *         self.left = nil
 10  *         self.right = nil
 11  *     }
 12  * }
 13  */
 14 class Object {
 15     var depth: Int
 16     var minWidth: Int
 17     var maxWidth: Int
 18     
 19     init(_ depth: Int) {
 20         self.depth = depth
 21         self.minWidth = Int.max
 22         self.maxWidth = Int.min
 23     }
 24     
 25     func updateWidth(_ val: Int) {
 26         if (val < minWidth) {
 27             self.minWidth = val
 28         }
 29         if (val > maxWidth) {
 30             self.maxWidth = val
 31         }
 32     }
 33     
 34     func getWidth() -> Int {
 35         var temp = maxWidth - minWidth
 36         print("max: \(maxWidth), min: \(minWidth)")
 37         if (maxWidth < 0 && minWidth < 0 || maxWidth > 0 && minWidth > 0) {
 38             temp += 1
 39         }
 40         if (temp == 0) { temp = 1 }
 41         
 42         return temp
 43     }
 44 }
 45 
 46 class Solution {
 47     func widthOfBinaryTree(_ root: TreeNode?) -> Int {
 48         if (root == nil) { return 0 }
 49         
 50         var width: [Object] = []
 51         
 52         bfs(root, 0, 0, &width)
 53         
 54         var max = 0
 55         for i in 0..<width.count {
 56             var tempWidth = width[i].getWidth()
 57             if (tempWidth > max) {
 58                 max = tempWidth
 59             }
 60         }
 61         
 62         return max
 63     }
 64     
 65     func bfs(_ node: TreeNode?, _ depth: Int, _ width: Int , _ arr: inout [Object]) {
 66         if (arr.count < depth+1) { arr.append(Object.init(depth)) }
 67         arr[depth].updateWidth(width)
 68         
 69         if (node!.left == nil && node!.right == nil) {
 70             return
 71         }
 72         
 73         if (node!.left != nil) {
 74             var temp = 0
 75             if (width < 0) {
 76                 temp = width &* 2
 77             }
 78             else if (width > 0) {
 79                 temp = width &* 2 - 1
 80             }
 81             else {
 82                 temp = -1
 83             }
 84 
 85             bfs(node!.left, depth+1, temp, &arr)
 86         }
 87         
 88         if (node!.right != nil) {
 89             var temp = 0
 90             if (width < 0) {
 91                 temp = width &* 2 + 1
 92             }
 93             else if (width > 0) {
 94                 temp = width &* 2
 95             }
 96             else {
 97                 temp = 1
 98             }
 99             
100             bfs(node!.right, depth+1, temp, &arr)
101         }
102     }
103 }

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     func widthOfBinaryTree(_ root: TreeNode?) -> Int {
16         guard let node = root else {
17             return 0
18         }
19         
20         var res = 1
21         var queue = [TreeNode?]()
22         var next = [TreeNode?]()
23         var cur = 0
24         queue.append(node)
25 
26         while !queue.isEmpty {
27             next.removeAll()
28             cur = 0
29             while cur < queue.count {
30                 let theNode = queue[cur]
31 
32                 next.append(theNode?.left)
33                 next.append(theNode?.right)
34 
35                 cur += 1
36             }
37             
38             queue = getArray(next)
39 
40             if res < queue.count {
41                 res = queue.count
42             }
43         }
44         return res
45     }
46     
47     func getArray(_ nodes: [TreeNode?]) -> [TreeNode?] {
48         guard nodes.count > 0 else {
49             return []
50         }
51         var left = 0
52         var right = nodes.count - 1
53         while left <= right && nodes[left] == nil  {
54             left += 1
55         }
56         while left <= right && nodes[right] == nil {
57             right -= 1
58         }
59         var res = [TreeNode?]()
60         while left <= right {
61             res.append(nodes[left])
62             left += 1
63         }
64         return res
65     }
66 }

172ms

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     
16     func trim(_ nodes: [TreeNode?]) -> [TreeNode?] {
17         var left = 0
18         var right = nodes.count - 1
19         while left < nodes.count && nodes[left] == nil {
20             left += 1
21         }
22         while right >= left && nodes[right] == nil {
23             right -= 1
24         }
25         if left > right {
26             return []
27         } else {
28             return Array(nodes[left...right])
29         }
30     }
31     
32     func widthOfBinaryTree(_ root: TreeNode?) -> Int {
33         guard let root = root else { return 0 }
34         var nodes: [TreeNode?] = [root]
35         var maxWidth = 1
36         while !nodes.isEmpty {
37             var nextNodes: [TreeNode?] = []
38             for node in nodes {
39                 nextNodes.append(node?.left)
40                 nextNodes.append(node?.right)
41             }
42             nodes = trim(nextNodes)
43             maxWidth = max(maxWidth, nodes.count)
44         }
45         return maxWidth
46     }
47 }

324ms

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     func widthOfBinaryTree(_ root: TreeNode?) -> Int {
16         guard let root = root else { return 0 }
17         
18         var queue: [TreeNode?] = [root]
19         var result = 0
20         
21         while queue.count > 0 {
22             result = max(result, queue.count)
23             
24             var nextQueue = [TreeNode?]()
25             
26             for node in queue {
27                 if !nextQueue.isEmpty || node?.left != nil {
28                     nextQueue.append(node?.left)
29                 }
30                 
31                 if !nextQueue.isEmpty || node?.right != nil {
32                     nextQueue.append(node?.right)
33                 }
34             }
35             
36             while nextQueue.last != nil && nextQueue.last! == nil {
37                 nextQueue.removeLast()
38             }
39             
 
                       
                    
                     
                      



鲜花




握手




雷人




路过




鸡蛋