🍣

NeetCode 150 [Trees]:easy 1/3

2025/01/23に公開

NeetCodeのSolutionを書いていく

Invert Binary Tree

2分木を反転する。
2分木のルートが与えられるので、反転しましょう。
反転、昇順を降順、みたいなことではなく、左右の葉っぱの位置を変えましょう。と言う問題。

処理時間:O(n)
メモリ:O(n)

メモリがO(n)ってことは、Treeを丸々コピーしてもOKってことね。
再帰も使っていいってことか。
何だろ、頭から代入していけばいいのでは?違うのかな?

現在のルートを新しいルートに設定。
現在の左の子を新しい右の子に設定。
同、右を左に設定。
そっか、ここで、「現在の左の子の左の孫」は「新しい右の子の右」になるわけか。
なんかちょっとめんどいかと思ったけどそうでもないか?

単純に再帰でできた!

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

Maximum Depth of Binary Tree

2分木のルートを渡すので深さを返してください。

処理時間:O(n)
メモリ:O(n)

これもメモリ0(n)か、再帰かな?

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        right_depth = left_depth = 0
        if not root:
            return 0

        if root.right:
            right_depth = self.maxDepth(root.right)
        
        if root.left:
            left_depth = self.maxDepth(root.left)
        
        return max(right_depth, left_depth) + 1

これでいけたが、なんか頭が混乱する・・・
左右の最大深さを取得、一つ上があるので+1する。
最後は0を返す

だんだん回答を読むのがきつくなってきた。
まだeasyなのに 🥲

Discussion