[Swift]LeetCode958.二叉树的完全性检验|CheckCompletenessofaBinaryTree

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

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

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

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

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

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

Given a binary tree, determine if it is a complete binary tree.

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Example 1:

Input: [1,2,3,4,5,6]
Output: true
Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.

Example 2:

Input: [1,2,3,4,5,null,7]
Output: false
Explanation: The node with value 7 isn't as far left as possible.

Note:

The tree will have between 1 and 100 nodes.

给定一个二叉树，确定它是否是一个完全二叉树。

百度百科中对完全二叉树的定义如下：

若设二叉树的深度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。（注：第 h 层可能包含 1~ 2h 个节点。）

示例 1：

输入：[1,2,3,4,5,6]
输出：true
解释：最后一层前的每一层都是满的（即，结点值为 {1} 和 {2,3} 的两层），且最后一层中的所有结点（{4,5,6}）都尽可能地向左。

示例 2：

输入：[1,2,3,4,5,null,7]
输出：false
解释：值为 7 的结点没有尽可能靠向左侧。

提示：

树中将会有 1 到 100 个结点。

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 isCompleteTree(_ root: TreeNode?) -> Bool {
16         var qs = [root]
17         while !qs.isEmpty {
18             let v = qs.count
19             for i in 0 ..< v {
20                 guard let u = qs.remove(at: 0) else {
21                     continue
22                 }
23                 var child = [u.left, u.right]
24                 for c in child {
25                     guard let t = c else {
26                         qs.append(c)
27                         continue
28                     } 
29                     if qs.count > 0, let t = qs.last, t == nil {
30                         return false
31                     }
32                     qs.append(c)
33                 }  
34 
35             }
36         }
37         return true
38     }
39 }

36 ms

 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 isCompleteTree(_ root: TreeNode?) -> Bool {
16         var root = root
17         var queue:[TreeNode?] =  [TreeNode?]()
18         var leaf:Bool = false
19         queue.append(root)
20         
21         while(!queue.isEmpty)
22         {
23             root = queue.removeFirst()
24             if (leaf && (root?.left != nil || root?.right != nil)) || (root?.left == nil && root?.right != nil)
25             {
26                 return false
27             }
28             if root?.left != nil
29             {
30                 queue.append(root?.left)
31             }
32             if root?.right != nil
33             {
34                 queue.append(root?.right)
35             }
36             else
37             {
38                 leaf = true
39             }
40         }
41          return true
42     }
43 }

36ms

 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 extension TreeNode {
15     public func height() -> Int {
16         if self.left == nil && self.right == nil {
17             return 1
18         }
19         var left = 0, right = 0
20         if self.left != nil {
21             left = self.left!.height()
22         }
23         if self.right != nil {
24             right = self.right!.height()
25         }
26         return 1 + max(left, right)
27     }
28 }
29 
30 class Solution {
31     func isCompleteTree(_ root: TreeNode?) -> Bool {
32         guard let first = root else { return true }
33         var level = first.height()
34         var arr: [TreeNode?] = [first]
35         var newArr: [TreeNode?] = []
36         // Construct array
37         while level > 2 {
38             newArr = []
39             for node in arr {
40                 if node != nil && node?.left != nil && node?.right != nil {
41                     newArr.append(node?.left)
42                     newArr.append(node?.right)
43                 } else {
44                     return false
45                 }
46             }
47             arr = newArr
48             level -= 1
49         }
50         
51         
52         // Assess last row
53         var foundNil = false
54         for node in arr {
55             // 1) If right node exists and left doesnt, return false
56             if node?.right != nil && node?.left == nil {
57                 return false
58             }
59             // 2) If a nil was found, no subsequent node children should have values else return false
60             if foundNil && (node?.left != nil || node?.right != nil) {
61                 return false
62             }
63             // 3) Notify a nil was found
64             if node?.left == nil || node?.right == nil {
65                 foundNil = true
66             }
67         }
68         return true
69     }
70 }

40ms

 1 extension TreeNode {
 2     func elements() -> [Int?] {
 3         let result: [Int?] = [self.val]
 4         return elementsRec(queue: [self], result: result)
 5     }
 6     
 7     func elementsRec(queue: [TreeNode], result: [Int?]) -> [Int?] {
 8         var innerQueue = queue
 9         
10         if innerQueue.isEmpty {
11             return result
12         }
13         
14         let tree = innerQueue.removeFirst()
15         
16         var innerResult = result
17         
18         if tree.left == nil && tree.right == nil {
19             innerResult.append(nil)
20             innerResult.append(nil)
21             return elementsRec(queue: innerQueue, result: innerResult)
22         }
23         
24         if let left = tree.left {
25             innerQueue.append(left)
26             innerResult.append(left.val)
27         } else {
28             innerResult.append(nil)
29         }
30         
31         if let right = tree.right {
32             innerQueue.append(right)
33             innerResult.append(right.val)
34         } else {
35             innerResult.append(nil)
36         }
37         
38         return elementsRec(queue: innerQueue, result: innerResult)
39     }
40 }
41     
42 class Solution {
43     func isCompleteTree(_ root: TreeNode?) -> Bool {  
44         guard let root = root else {
45             return true
46         }
47         
48         let elements = root.elements()
49         
50         var hasNull = false
51         
52         for i in 0..<elements.count {
53             let element = elements[i]
54             
55             if element == nil {
56                 
57                 hasNull = true
58                 continue
59                 
60             } else {
61                 
62                 if hasNull {
63                     return false
64                 }
65                 
66                 hasNull = false
67             }
68         }
69         
70         if root.left == nil && root.right != nil {
71             return false
72         }
73         
74         return isCompleteTree(root.left) && isCompleteTree(root.right)
75     }
76 }