[leetcode 104] Maximum Depth of Binary Tree

6185 ワード
アルゴリズム#アルゴリズム# 道しるべ コセット テキストリンク
質問リンク
マイロジック
ツリーの最大深さの問題を探します.ということで、どうしても木の根から木の葉ノードまで巡回し、木の巡回なら前列巡回、中列巡回、後列巡回があると思います.この考えは毎回再帰的であり,再帰的に考えを実現すると,再帰関数を置く位置だけが変わる.この問題では,どの順番で巡回しても構わず,いかなる巡視方式を用いてもよい.
巡回後、左または右の幹線から戻ってきたノードの深さをmax関数と比較し、次の手順に従います.
ループで最大ノードの深さを維持し、最終的に戻ります.
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        
        def traverse(node, num):
            
            if not node.left  and not node.right:
                return num
            
            ret = num
            if node.right:
                ret = max(ret, traverse(node.right,num+1))
            if node.left:
                ret = max(ret,traverse(node.left, num+1))
                          
            return ret
                          
                          
        return traverse(root, 1) if root != None else 0
本のロジック
本の中でBFSで説明します.
ルートノードで接続されたサブノードを順次ナビゲートし、親ノードにアクセスするたびに深さが増加します.
    def maxDepth(self, root: TreeNode) -> int:
        
        if not root:
            return 0
        
        queue = collections.deque([root])
        depth = 0
        
        while queue:
            depth += 1
            
            for _ in range(len(queue)):
                
                cur = queue.popleft()
                if cur.right:
                    queue.append(cur.right)
                if cur.left:
                    queue.append(cur.left)
                    
        return depth
カスタムViewで雨の落下効果を実現
2ヶ月以上の設計とコードをして、私はFlutterの動態化の方案の対比と最良の実現を整理しました