問題
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のコーディングインタビューも余裕なのではないでしょうか。
回答
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)