🍣
NeetCode 150 [Trees]:easy 1/3
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