[Swift]LeetCode919.完全二叉树插入器|CompleteBinaryTreeInserter

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

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

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

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

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

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

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

Write a data structure CBTInserter that is initialized with a complete binary tree and supports the following operations:

CBTInserter(TreeNode root) initializes the data structure on a given tree with head node root;
CBTInserter.insert(int v) will insert a TreeNode into the tree with value node.val = v so that the tree remains complete, and returns the value of the parent of the inserted TreeNode;
CBTInserter.get_root() will return the head node of the tree.

Example 1:

Input: inputs = [[[1]],[2],[]]
Output: [null,1,[1,2]]

Example 2:

Input: inputs = [[[1,2,3,4,5,6]],[7],[8],[]]
Output: [null,3,4,[1,2,3,4,5,6,7,8]]

Note:

The initial given tree is complete and contains between 1 and 1000 nodes.
CBTInserter.insert is called at most 10000 times per test case.
Every value of a given or inserted node is between 0 and 5000.

完全二叉树是每一层（除最后一层外）都是完全填充（即，结点数达到最大）的，并且所有的结点都尽可能地集中在左侧。

设计一个用完全二叉树初始化的数据结构 CBTInserter，它支持以下几种操作：

CBTInserter(TreeNode root) 使用头结点为 root 的给定树初始化该数据结构；
CBTInserter.insert(int v) 将 TreeNode 插入到存在值为 node.val = v 的树中以使其保持完全二叉树的状态，并返回插入的 TreeNode 的父结点的值；
CBTInserter.get_root() 将返回树的头结点。

示例 1：

输入：inputs = ["CBTInserter","insert","get_root"], inputs = [[[1]],[2],[]]
输出：[null,1,[1,2]]

示例 2：

输入：inputs = ["CBTInserter","insert","insert","get_root"], inputs = [[[1,2,3,4,5,6]],[7],[8],[]]
输出：[null,3,4,[1,2,3,4,5,6,7,8]]

提示：

最初给定的树是完全二叉树，且包含 1 到 1000 个结点。
每个测试用例最多调用 CBTInserter.insert 操作 10000 次。
给定结点或插入结点的每个值都在 0 到 5000 之间。

68ms

 1 class CBTInserter {
 2 
 3   var root: TreeNode?
 4   var nodeArray = [TreeNode]()
 5 
 6   init(_ root: TreeNode?) {
 7     self.root = root
 8     var nextLevelStack = [TreeNode]()
 9     if let node = root {
10       nextLevelStack.append(node)
11     }
12 
13     while nextLevelStack.count > 0 {
14       let levelStack = nextLevelStack
15       nextLevelStack = [TreeNode]()
16       for node in levelStack {
17         nodeArray.append(node)
18         if let left = node.left {
19           nextLevelStack.append(left)
20         }
21         if let right = node.right {
22           nextLevelStack.append(right)
23         }
24       }
25     }
26   }
27 
28   func insert(_ v: Int) -> Int {
29     let newNode = TreeNode(v)
30     let newIndex = 1 + nodeArray.count
31     if newIndex <= 1 {
32       root = newNode
33       nodeArray.append(newNode)
34       return 0
35     }
36 
37     let parentIndex = newIndex / 2
38     let parentNode = nodeArray[parentIndex - 1]
39     if newIndex % 2 == 0 {
40       parentNode.left = newNode
41     } else {
42       parentNode.right = newNode
43     }
44     nodeArray.append(newNode)
45     return parentNode.val
46   }
47 
48   func get_root() -> TreeNode? {
49     return root
50   }
51 }

72ms

  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 
 15 class CBTInserter {
 16     var arr: [TreeNode] = []
 17 
 18     init(_ root: TreeNode?) {
 19         guard let root = root else { return }
 20         let q = Queue<TreeNode>()
 21         q.enqueue(root)
 22         while !q.isEmpty {
 23             var node = q.dequeue()!
 24             arr.append(node)
 25             if node.left != nil {
 26                 q.enqueue(node.left!)
 27             }
 28             if node.right != nil {
 29                 q.enqueue(node.right!)
 30             }
 31         }
 32     }
 33 
 34     func insert(_ v: Int) -> Int {
 35         let node = TreeNode(v)
 36         let index = arr.count
 37         arr.append(node)
 38         let parent = (index - 1)/2
 39         if parent >= 0 {
 40             let par = arr[parent]
 41             if (2*parent + 1) == index {
 42                 par.left = node
 43             } else {
 44                 par.right = node
 45             }
 46             return par.val
 47         } else {
 48             return 0
 49         }
 50     }
 51 
 52     func get_root() -> TreeNode? {
 53         return arr.first
 54     }
 55 }
 56 
 57 public class Queue<T> {
 58   fileprivate var array = [T?]()
 59   fileprivate var head = 0
 60 
 61   public var isEmpty: Bool {
 62     return count == 0
 63   }
 64 
 65   public var count: Int {
 66     return array.count - head
 67   }
 68 
 69   public func enqueue(_ element: T) {
 70     array.append(element)
 71   }
 72 
 73   public func dequeue() -> T? {
 74     guard head < array.count, let element = array[head] else { return nil }
 75 
 76     array[head] = nil
 77     head += 1
 78 
 79     let percentage = Double(head)/Double(array.count)
 80     if array.count > 50 && percentage > 0.25 {
 81       array.removeFirst(head)
 82       head = 0
 83     }
 84 
 85     return element
 86   }
 87 
 88   public var front: T? {
 89     if isEmpty {
 90       return nil
 91     } else {
 92       return array[head]
 93     }
 94   }
 95 }
 96 
 97 /**
 98  * Your CBTInserter object will be instantiated and called as such:
 99  * let obj = CBTInserter(root)
100  * let ret_1: Int = obj.insert(v)
101  * let ret_2: TreeNode? = obj.get_root()
102  */
103

76ms

 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 
15 class CBTInserter {
16     var root: TreeNode?
17     var total = 0
18     init(_ root: TreeNode?) {
19         self.root = root
20         count(root)
21         //print(total)
22     }
23     
24     func count(_ r: TreeNode?) {
25         guard let r = r else {
26             return
27         }
28         total += 1
29         count(r.left)
30         count(r.right)
31     }
32 
33     func insert(_ v: Int) -> Int {
34         total += 1
35         let bs = String(total, radix: 2)
36         //print(bs)
37         var p = root
38         for i in 1 ..< bs.count {
39             let b = bs[bs.index(bs.startIndex, offsetBy: i)]
40             let q = b == "0" ? p?.left : p?.right
41             if q == nil {
42                 if b == "0" {
43                     p?.left = TreeNode(v)
44                 }
45                 else {
46                     p?.right = TreeNode(v)
47                 }
48                 return p!.val
49             }
50             p = q
51         }
52         return -1
53     }
54 
55     func get_root() -> TreeNode? {
56         return root
57     }
58 }
59 
60 /**
61  * Your CBTInserter object will be instantiated and called as such:
62  * let obj = CBTInserter(root)
63  * let ret_1: Int = obj.insert(v)
64  * let ret_2: TreeNode? = obj.get_root()
65  */

80ms

 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 
15 class CBTInserter {
16     var root:TreeNode?
17     var deque:[TreeNode?] = [TreeNode?]()
18     init(_ root: TreeNode?) {
19         self.root = root
20         var queue:[TreeNode?] = [TreeNode?]()
21         queue.append(root)
22         
23         // BFS to populate deque
24         while(!queue.isEmpty)
25         {
26            var node:TreeNode? = queue.removeFirst()
27             if node?.left == nil || node?.right == nil
28             {
29                 deque.append(node)
30             }
31             
32             if node?.left != nil
33             {
34                 queue.append(node?.left)
35             }
36             if  node?.right != nil
37             {
38                 queue.append(node?.right)
39             }
40         }
41     }
42 
43     func insert(_ v: Int) -> Int {
44         var node:TreeNode? = deque.first!
45         deque.append(TreeNode(v))
46         if node?.left == nil
47         {
48             node?.left = deque.last!
49         }
50         else
51         {
52             node?.right = deque.last!
53             deque.removeFirst()
54         }
55         return node!.val
56     }
57 
58     func get_root() -> TreeNode? {
59         return root
60     }
61 }