binary_tree_level_order_traversal

View Source

 1from typing import Optional
 2from utils import TreeNode
 3from collections import deque
 4
 5
 6# @leet start
 7# Definition for a binary tree node.
 8# class TreeNode:
 9#     def __init__(self, val=0, left=None, right=None):
10#         self.val = val
11#         self.left = left
12#         self.right = right
13class Solution:
14    def levelOrder(self, root: Optional[TreeNode]) -> list[list[int]]:
15        """
16        This function returns the level order traversal of a binary tree.
17        It does this by BFSing through the nodes, and keeping the level
18        of each node during the traversal.
19
20        This could be made terser by using a defaultdict (so you dont have to initialize
21        any of the lists by level.
22        """
23        if not root:
24            return []
25        res = []
26        q = deque([(root, 0)])
27
28        while q:
29            node, level = q.popleft()
30            if len(res) <= level:
31                res.append([])
32            res[level].append(node.val)
33            if node.left:
34                q.append((node.left, level + 1))
35            if node.right:
36                q.append((node.right, level + 1))
37
38        return res
39
40
41# @leet end
42
43
44def test():
45    assert 2 + 2 == 4

class Solution: View Source

14class Solution:
15    def levelOrder(self, root: Optional[TreeNode]) -> list[list[int]]:
16        """
17        This function returns the level order traversal of a binary tree.
18        It does this by BFSing through the nodes, and keeping the level
19        of each node during the traversal.
20
21        This could be made terser by using a defaultdict (so you dont have to initialize
22        any of the lists by level.
23        """
24        if not root:
25            return []
26        res = []
27        q = deque([(root, 0)])
28
29        while q:
30            node, level = q.popleft()
31            if len(res) <= level:
32                res.append([])
33            res[level].append(node.val)
34            if node.left:
35                q.append((node.left, level + 1))
36            if node.right:
37                q.append((node.right, level + 1))
38
39        return res

def levelOrder(self, root: Optional[utils.TreeNode]) -> list[list[int]]: View Source

15    def levelOrder(self, root: Optional[TreeNode]) -> list[list[int]]:
16        """
17        This function returns the level order traversal of a binary tree.
18        It does this by BFSing through the nodes, and keeping the level
19        of each node during the traversal.
20
21        This could be made terser by using a defaultdict (so you dont have to initialize
22        any of the lists by level.
23        """
24        if not root:
25            return []
26        res = []
27        q = deque([(root, 0)])
28
29        while q:
30            node, level = q.popleft()
31            if len(res) <= level:
32                res.append([])
33            res[level].append(node.val)
34            if node.left:
35                q.append((node.left, level + 1))
36            if node.right:
37                q.append((node.right, level + 1))
38
39        return res

This function returns the level order traversal of a binary tree. It does this by BFSing through the nodes, and keeping the level of each node during the traversal.

This could be made terser by using a defaultdict (so you dont have to initialize any of the lists by level.

def test(): View Source

45def test():
46    assert 2 + 2 == 4