pco2699’s blog

学んだものについて、メモしておく場所

LeetCode: Invert Binary Treeを解く

問題

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

leetcode.com

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

訳すると、

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

計算量

再帰だと関数の呼び出しスタックに積まれるため 例えば左にめちゃくちゃ偏った木だと最悪のO(n)になります。
時間計算量: O(n)
空間計算量: O(n)