LeetCode: Invert Binary Treeを解く

問題

June Leetcoding Challange Complementの1日目です。
まさかの3か月目突入に自分も驚きが隠せません！

ちなみに、この問題はHomebrewの作者がGoogleに落ちた際に、コーディングインタビューの無意味さに対して
ブチ切れたこのツイートで有名になった問題です。

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.
— Max Howell (@mxcl) 2015年6月10日

訳すると、

Google 「90%の弊社のエンジニアはお前の書いたソフト(Homebrew)使ってるけど、二分木も反転させられないから消え失せな！」

自分は逆にこんなすごい人でもGoogleに落ちるんだな、ということでびっくりした覚えがあります。

解き方

Homebrewの作者は解けなかったようですが、この問題別にそんなに難しくありません。二分木のこういう問題は、再帰を利用すれば簡単に解けます。

詳しくはこの動画の6:54から見てみてください。 youtu.be

ちなみに、このブログで何回か紹介していますが、Back To Back SWEは数あるアルゴリズム解説動画の中でも屈指の分かりやすさと丁寧さです。
アルゴリズムの網羅性も高いので、このチャンネルの動画全部見てしっかり理解すれば G〇〇gleのコーディングインタビューも余裕なのではないでしょうか。

www.youtube.com

回答

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return
        
        orgRight = root.right
        root.right = self.invertTree(root.left)
        root.left = self.invertTree(orgRight)
        
        return root