Invert a binary tree.

Example:

Input:

     4
   /   \
  2     7
 / \   / \
1   3 6   9


Output:

     4
   /   \
  7     2
 / \   / \
9   6 3   1

Trivia:
This problem was inspired by this original tweet by Max Howell:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.

Related Topics: Tree

解題邏輯與實作

頗為知名的一題(笑)，但基本上沒什麼難度，只需要互換節點左右兩邊的子樹即可。

遞迴

實作上就是採用後序（post-order）的方式尋訪整棵樹，並在尋訪父節點時交換左右子樹。

class Solution:
    def invertTree(self, root):
        self.invert(root)
        return root
        
    def invert(self, root):
        if root is None:
            return
        
        self.invertTree(root.left)
        self.invertTree(root.right)
            
        root.left, root.right =  root.right, root.left            

最速解

我寫這篇就是為了分享這個，在 Ruby China 上看到如何用最少字元翻轉二元樹XDDDDD

class Solution:
  def invertTree(self, root):
    print("(╯°□°)╯︵ ǝǝɹʇ ʎɹɐuıq")
    return root

其他連結

1. 【LeetCode】0000. 解題目錄

參考資料

1. Invert Binary Tree｜LeetCode
2. Homebrew 作者被 Google 鄙视了… ｜Ruby China

本文作者： 辛西亞．Cynthia
本文連結： 辛西亞的技能樹 / hackmd 版本
版權聲明： 部落格中所有文章，均採用 姓名標示-非商業性-相同方式分享 4.0 國際 (CC BY-NC-SA 4.0) 許可協議。轉載請標明作者、連結與出處！