NeetCodeのSolutionを書いていく #
Diameter of Binary Tree #
https://neetcode.io/problems/binary-tree-diameter
neetcode.io
2分木の最も長いパスの長さを直径といいいます。 長さはノード間のエッジの数です。 直径はrootを通る必要はありません。 二分木のrootを与えるので、直径を返しなさい。
処理時間：O(n) メモリ：O(n)
これもメモリがO(n)だから再帰かな？ それぞれのノードの組み合わせ間のエッジを数えると組み合わせが多くなっちゃう。 わからん・・・
ヒント見ちゃった。
直径は右と左の高さの加算値の最大値です
ううむ確かにその通りだ。 てことは枝をたどりながら最大値を更新していけばいいか？
class Solution:
diameter = 0
def calcdiameter(self, root: Optional[TreeNode]) -> int:
if (not root):
return 0
else:
left = self.calcdiameter(root.left) + 1 if root.left else 0
right = self.calcdiameter(root.right) + 1 if root.right else 0
if self.diameter < (left + right):
self.diameter = (left + right)
return max(left, right)
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
self.calcdiameter(root)
return self.diameter
これでいけた。 枝を追いながら深さを追加しつつ、左右の枝の深さの加算値の最大値を更新する。 これならそれぞれのノードを一度参照する再帰なので、計算量O(n)、メモリO(n)を達成できるか。
しかしeasyもむずいな。。。
Balanced Binary Tree #
https://neetcode.io/problems/balanced-binary-tree
neetcode.io
バイナリツリーが与えられます。 高さのバランスが取れているときはtrueをそうでない場合はfalseを返します。 バランスが取れているとは、全てのノードの左右の深さの差が0か1のものとします。
処理時間：O(n) メモリ：O(n)
これは簡単か？ さっきやったleftとrightの差が1より大きくなったらfalseを返せば良い。
class Solution:
result = True
def calcdiameter(self, root: Optional[TreeNode]) -> int:
if (not root):
return 0
else:
left = self.calcdiameter(root.left) + 1 if root.left else 0
right = self.calcdiameter(root.right) + 1 if root.right else 0
if abs(left-right) > 1:
self.result = False
return max(left, right)
def isBalanced(self, root: Optional[TreeNode]) -> int:
self.calcdiameter(root)
return self.result