iOS Interview - Leetcode 226. Invert Binary Tree

May 03, 20242 min read#swift, #interview, #leetcode

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
Quick Drop logo

Profile picture

Personal blog by An Tran. I'm focusing on creating useful apps.
#Swift #Kotlin #Mobile #MachineLearning #Minimalist


© An Tran - 2024