Leetcode: 226. Invert Binary Tree
- Primary idea: Recursively invert left and right nodes
- Time Complexity: O(n)
- Space Complexity: O(n)
public class TreeNode {
public var val: Int
public var left: TreeNode?
public var right: TreeNode?
public init() { self.val = 0; self.left = nil; self.right = nil; }
public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
self.val = val
self.left = left
self.right = right
}
}
extension TreeNode {
public func printTree() {
printTreeHelper(self, "", true)
}
private func printTreeHelper(_ node: TreeNode?, _ prefix: String, _ isLeft: Bool) {
guard let node = node else { return }
let arrow = isLeft ? "┣━━" : "┗━━"
let branch = isLeft ? "┃ " : " "
print(prefix + arrow + " " + "\(node.val)")
printTreeHelper(node.left, prefix + branch, true)
printTreeHelper(node.right, prefix + branch, false)
}
}
func invertTree(_ root: TreeNode?) -> TreeNode? {
guard let root = root else { return nil }
let left = invertTree(root.left)
let right = invertTree(root.right)
root.left = right
root.right = left
return root
}
//let node1 = TreeNode(2)
//node1.left = TreeNode(1)
//node1.right = TreeNode(3)
//node1.printTree()
////┣━━ 2
////┃ ┣━━ 1
////┃ ┗━━ 3
//invertTree(node1)?.printTree()
////┣━━ 2
////┃ ┣━━ 3
////┃ ┗━━ 1
let node2 = TreeNode(4)
let node21 = TreeNode(2)
let node22 = TreeNode(7)
node2.left = node21
node2.right = node22
node21.left = TreeNode(1)
node21.right = TreeNode(3)
node22.left = TreeNode(6)
node22.right = TreeNode(9)
node2.printTree()
//┣━━ 4
//┃ ┣━━ 2
//┃ ┃ ┣━━ 1
//┃ ┃ ┗━━ 3
//┃ ┗━━ 7
//┃ ┣━━ 6
//┃ ┗━━ 9
invertTree(node2)?.printTree()
//┣━━ 4
//┃ ┣━━ 7
//┃ ┃ ┣━━ 9
//┃ ┃ ┗━━ 6
//┃ ┗━━ 2
//┃ ┣━━ 3
//┃ ┗━━ 1