いいものをつくろう

CTOの日記

アルゴリズム

【アルゴリズム脳トレ】leetcode medium 222 Count Complete Tree Nodes

投稿日:

こんにちは

今回の学びは

・パターンによってO(N)かO(logN)になって良い。それでも立派な改善だ!

 

問題はcount-complete-tree-nodes

(時間配分は5分問題理解=restate&clarify 10分検討multip-sol, analysis, reasons 10分実装  20分振り返り の一文45分構成)をできればgoogle docで笑&真剣。

終始、わからないことは声にだして、明確にしていきましょう。

1,まずは入出力をしっかりおさえましょう。(問題を自分の言葉で復唱すること、わからないことをクリアにすると、前提も声にだすこと)

 

2,いくつかのソリューションを声にだして出してみましょう。(もちろんtime complexit, space complexityの分析や理由を付け加えて)

 

3,どれでいくか、一緒に決定しましょう。(理由付きでね、よろしく)

timespace analysis (時間とスペースの分析)は 〇〇です

 

最初はDFSの回答しかわからなかった。

高さからの公式で出すのは、わかったがそれをコードにはできなかった。なぜなら、何個欠けているのか?

それを判別するためには結局O(N)回るひつようがあるとおもった。

ところが、それでも良い、と言っているのが今回の問題です、それが最大の収穫となりました。

 

 

4、実装しましょう。

# 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)
    
            

この動画が理解に役立ちました。

 

5、エッジケースとサンプルテストを忘れずに!

 

 

 

振り返り

「次のこの問題を解くばあい知っていればよい一つの事実とは?」

・パターンによってO(N)かO(logN)になって良い。それでも立派な改善だ!

 

 

まとめ

 

以上です

-アルゴリズム
-

Copyright© CTOの日記 , 2020 All Rights Reserved.