226 Invert Binary Tree

• 翻轉二元樹（左右子樹交換）。
• Kotlin, DFS

class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

fun invertTree(root: TreeNode?): TreeNode? {
    if (root == null) return null
    val tmp = root.left
    root.left = invertTree(root.right)
    root.right = invertTree(tmp)
    return root
}

• follow up
  • 你會怎麼用 BFS（迭代）來做？
  • 如果樹是非常深（上萬層），遞迴會有 StackOverflow，怎麼處理？
  • 這題其實是 LeetCode 的經典 easy，但面試官可能會問你是否能在原地翻轉、空間複雜度是多少。
  • 如果二元樹是 n-ary tree，怎麼翻轉？