Invert Binary Tree
Understand and solve the interview question "Invert Binary Tree".
We'll cover the following...
Description
In this lesson, your task is to invert a given binary tree, T
.
Let’s look at an example below:
main.swift
TreeNode.swift
import Swiftfunc invertTree(root: TreeNode?) -> TreeNode? {return root}
Invert binary tree exercise
Solution
We can solve this problem using depth-first search (DFS).
The inverse of an empty tree is the empty tree. To invert tree T
with root
and subtrees left
and right
, we keep root the same and invert the right
and left
subtrees.
Let’s review the implementation below:
main.swift
TreeNode.swift
import Swiftfunc invertTree(root: TreeNode?) -> TreeNode? {if root == nil {return root}let right: TreeNode? = invertTree(root: root!.right)let left: TreeNode? = invertTree(root: root!.left)root!.left = rightroot!.right = leftreturn root}func helper(node: TreeNode?, level: Int, levels: inout [[Int]]) {// start the current levelif levels.count == level {levels.append([])}// fulfil the current levellevels[level].append(node!.val)// process child nodes for the next levelif node!.left != nil {helper(node: node!.left, level: level + 1, levels: &levels)}if node!.right != nil {helper(node: node!.right, level: level + 1, levels: &levels)}}func to_string(vec: [[Int]]) -> String{var str = "["var i: Int = 0var j: Int = 0while i < vec.count {str += "["j = 0while j < vec[i].count {str += String(vec[i][j])if j + 1 < vec[i].count {str += ", "}j += 1}str += "]"if i + 1 < vec.count {str += ", "}i += 1}str += "]"return str}func levelOrder(root: TreeNode?) -> [[Int]] {var levels: [[Int]] = []if root == nil { return levels }helper(node: root, level: 0, levels: &levels)return levels}func Print(root: TreeNode?){let vec: [[Int]] = levelOrder(root: root)print(to_string(vec: vec))}let root: TreeNode = TreeNode(x: 1)root.left = TreeNode(x: 2)root.right = TreeNode(x: 3)root.left!.left = TreeNode(x: 4)root.left!.right = TreeNode(x: 5)root.right!.left = TreeNode(x: 6)root.right!.right = TreeNode(x: 7)let res: TreeNode? = invertTree(root: root)Print(root: root)
Invert binary tree solution
Complexity measures
Time Complexity | Space Complexity |
---|---|