NeetCodeのSolutionを書いていく #
Invert Binary Tree #
https://neetcode.io/problems/invert-a-binary-tree
neetcode.io
２分木を反転する。 ２分木のルートが与えられるので、反転しましょう。 反転、昇順を降順、みたいなことではなく、左右の葉っぱの位置を変えましょう。と言う問題。
処理時間：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 #
https://neetcode.io/problems/depth-of-binary-tree
neetcode.io
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なのに 🥲
Reply by Email