Problem Statement
Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree
{3,9,20,#,#,15,7},
|
1 2 3 4 5 |
3 / \ 9 20 / \ 15 7 |
return its bottom-up level order traversal as:
|
1 2 3 4 5 |
[ [15,7], [9,20], [3] ] |
Original LeetCode problem page
My Solution in Swift
This is how TreeNode class looks like:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
class TreeNode { var val: Int var left: TreeNode? var right: TreeNode? init(val: Int) { self.val = val } convenience init(val: Int, left: TreeNode?, right: TreeNode?) { self.init(val: val) self.left = left self.right = right } } |
I used tail recursion technique to make the recursive approach faster. The following is my recursive version of Bottom-up Breadth-first traversal (aka bottom-up level order traversal) of a binary search tree:
|
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 |
func recursiveLevelOrderBottom(root: TreeNode?) -> [[Int]] { if root == nil { return [] } return _recursiveLevelOrderBottom([root!], []).reverse() } func _recursiveLevelOrderBottom(queue: [TreeNode], resultSoFar: [[Int]]) -> [[Int]] { var result: [Int] = [] var queueNext: [TreeNode] = [] for node in queue { result.append(node.val) if node.left != nil { queueNext.append(node.left!) } if node.right != nil { queueNext.append(node.right!) } } if queueNext.count == 0 { return resultSoFar + [result] } else { return _recursiveLevelOrderBottom(queueNext, resultSoFar + [result]) } } |
The iterative version of Bottom-up Breadth-first traversal (aka bottom-up level order traversal) of a binary search tree:
|
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 |
func iterativeLevelOrderBottom(root: TreeNode?) -> [[Int]] { if root == nil { return [] } var output: [[Int]] = [] var result: [Int] = [] var queue: [TreeNode] = [root!] var queueNext: [TreeNode] = [] while queue.count > 0 { for node in queue { result.append(node.val) if node.left != nil { queueNext.append(node.left!) } if node.right != nil { queueNext.append(node.right!) } } output.append(result) result.removeAll(keepCapacity: true) queue = queueNext queueNext.removeAll(keepCapacity: true) } return output.reverse() } |
Even using -O compilation flag, the recursive version is still slower than the iterative counterpart with 33 ms vs 6 ms. This doesn’t follow behaviours as depicted in Depth-first traversals (NLR, LNR, LRN). The main reason is that the recursive version has to pass intermediate results deep down along with those recursive function calls. Besides, the overhead of function calls is not negligible.
Try It Yourself
1: each links to a blog post of mine that is dedicated to the problem
2: total execution time of a solution on my MacBook Pro (Late 2013, 2.6 GHz Intel Core i7, 16 GB 1600 MHz DDR3). Each solution is compiled with following command:
$ swiftc -O -sdk `xcrun --show-sdk-path --sdk macosx` json.swift main.swift -o mySolution
The total execution time is the average of 10 runs.
3: these test cases are semi-automatically :P retrieved from LeetCode Online Judge system and are kept in JSON format
4: each Xcode project includes everything (my Swift solution to a problem, its JSON test cases and a driver code to test the solution on those test cases)
| Problem1 | Time2 | Test Cases3 | My Xcode Project4 |
| Binary Tree Level Order Traversal II | 5.797ms |