Problem Statement
Given a binary tree, return the postorder traversal of its nodes’ values.
For example:
Given binary tree
{1,#,2,3},
|
1 2 3 4 5 |
1 \ 2 / 3 |
return [3,2,1].
Note: Recursive solution is trivial, could you do it iteratively?
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 } } |
The recursive version of Postorder Depth-first traversal (aka Left-Right-Node (LRN) traversal) of a binary search tree:
|
1 2 3 4 5 6 7 8 9 10 |
func recursivePostorderTraversal(root: TreeNode?) -> [Int] { if root == nil { return [] } var result: [Int] = [] result += recursivePostorderTraversal(root!.left) result += recursivePostorderTraversal(root!.right) result.append(root!.val) return result } |
The iterative version of Postorder Depth-first traversal (aka Left-Right-Node (LRN) 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 iterativePostorderTraversal(root: TreeNode?) -> [Int] { if root == nil { return [] } var result: [Int] = [] var stack: [TreeNode] = [] var visitedNodes: NSMutableSet = NSMutableSet.set() var currNode: TreeNode! = root while currNode != nil { if currNode.left != nil && !visitedNodes.containsObject(currNode.left!) { stack.append(currNode) currNode = currNode.left! continue } if currNode.right != nil && !visitedNodes.containsObject(currNode.right!) { stack.append(currNode) currNode = currNode.right! continue } result.append(currNode.val) visitedNodes.addObject(currNode) currNode = stack.count > 0 ? stack.removeLast() : nil } return result } |
Obviously, using recursion to write the LRN is more straightforward. On the other hand, using iteration seems more efficient, because we don’t have to worry about those call stacks introduced by the recursion. Indeed, under debug mode (with -Onone compilation flag), the recursive and iterative LRN version of Swift code cost 21 ms and 12 ms respectively. The iterative version is about twice as fast as the recursive counterpart. However, when compiling with -O flag, the recursive version runs almost twice as fast as the iterative counterpart with execution time 1.8 ms vs 3.5 ms. Swift has done a great job at optimising the recursion. The slower speed of iterative LRN approach may be caused by my using of a hashset to keep record of what TreeNodes have been visited, in order to make sure that each TreeNode is only visited once. This also tries to make the traversal process non-destructive, so the process doesn’t change the content of the tree being traversed.
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 Postorder Traversal | 1.694ms |