バイナリ ツリー レベルの順序トラバーサル Leecode

バイナリ ツリーのルートを指定すると、そのノードの値のレベル順序の走査を返します。 (つまり、左から右へ、レベルごとに)。

Example 1:
Input: root = [3,9,20,null,null,15,7] 
Output: [[3],[9,20],[15,7]]

Example 2:
Input: root = [1]
Output: [[1]]

Example 3:
Input: root = []
Output: []

バイナリ ツリー レベルの順序トラバーサル Python ソリューション

class Solution(object):
    def levelOrder(self, root):
        if not root:
            return []
        Q = deque([root])
        levels = [[root.val]]
        temp = deque()
        while Q:
            node = Q.popleft()
            if node.left: temp.append(node.left)
            if node.right: temp.append(node.right)
            if not Q:
                if temp:
                    levels.append([n.val for n in temp])
                Q = temp
                temp = deque()
        return levels

このソリューションで使用されるコーディング パターン

提供されているすべての実装で使用されるコーディング パターンは、ツリー幅優先検索 (BFS) です。
このパターンは通常、ツリーをレベルごとに走査し、次の深さに移動する前に現在の深さのすべてのノードを処理します。
BFS は、キュー データ構造を使用して実装され、各レベルでノードを追跡します。

このソリューションの時間と空間の複雑さ

1. 各ノードは 1 回訪問されるため、時間計算量は O(N) です。
2. キュー (または再帰スタック) はどのレベルでもノードの最大数まで保持できるため、スペースの複雑さは O(M) です。

参考:

1. LeetCode の問題
2. リートコード ソリューション
3. 幅優先検索

以上がバイナリ ツリー レベルの順序トラバーサル Leecodeの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。