[LeetCode] 226. Invert Binary Tree

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.


解題邏輯與實作

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


遞迴

實作上就是採用後序(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. Invert Binary Tree - LeetCode
  2. Homebrew 作者被 Google 鄙视了… · Ruby China

留言

這個網誌中的熱門文章

Genymotion 模擬器安裝篇:In ubuntu14.04 LET