こんにちは
今回の学びは
・パターンによってO(N)かO(logN)になって良い。それでも立派な改善だ！
（時間配分は5分問題理解=restate&clarify 10分検討multip-sol, analysis, reasons 10分実装 20分振り返り の一文45分構成)をできればgoogle docで笑&真剣。
終始、わからないことは声にだして、明確にしていきましょう。
１，まずは入出力をしっかりおさえましょう。（問題を自分の言葉で復唱すること、わからないことをクリアにすると、前提も声にだすこと）
２，いくつかのソリューションを声にだして出してみましょう。（もちろんtime complexit, space complexityの分析や理由を付け加えて）
３，どれでいくか、一緒に決定しましょう。（理由付きでね、よろしく）
timespace analysis (時間とスペースの分析）は 〇〇です
最初はDFSの回答しかわからなかった。
高さからの公式で出すのは、わかったがそれをコードにはできなかった。なぜなら、何個欠けているのか？
それを判別するためには結局O(N)回るひつようがあるとおもった。
ところが、それでも良い、と言っているのが今回の問題です、それが最大の収穫となりました。
４、実装しましょう。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def countNodes(self, root: TreeNode) -> int:
if root is None: return 0
curr, leftn = root.left, 0
while curr:
leftn += 1
curr = curr.left
curr, rightn = root.right, 0
while curr:
rightn += 1
curr = curr.right
if leftn == rightn: # fully complete tree
return 2 ** (leftn+1) - 1
else:
return 1 + self.countNodes(root.left) + self.countNodes(root.right)
この動画が理解に役立ちました。
５、エッジケースとサンプルテストを忘れずに！
振り返り
「次のこの問題を解くばあい知っていればよい一つの事実とは？」
・パターンによってO(N)かO(logN)になって良い。それでも立派な改善だ！
まとめ
以上です