• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

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

原作者: [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:

  1. 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. 树中将会有 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 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
[Swift]LeetCode878.第N个神奇数字|NthMagicalNumber发布时间:2022-07-14
下一篇:
swift 类和结构体发布时间:2022-07-14
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap