LeetCode in Racket
102. Binary Tree Level Order Traversal
Medium
Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).
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: []
Constraints:
- The number of nodes in the tree is in the range
[0, 2000]. -1000 <= Node.val <= 1000
Solution
; Definition for a binary tree node.
#|
; val : integer?
; left : (or/c tree-node? #f)
; right : (or/c tree-node? #f)
(struct tree-node
(val left right) #:mutable #:transparent)
; constructor
(define (make-tree-node [val 0])
(tree-node val #f #f))
|#
(define (make-level-table table level node)
(if node
(let* ([table (hash-update table level
(lambda (lst) (cons (tree-node-val node) lst))
'())]
[table (make-level-table table (add1 level) (tree-node-right node))])
(make-level-table table (add1 level) (tree-node-left node)))
table))
(define/contract (level-order root)
(-> (or/c tree-node? #f) (listof (listof exact-integer?)))
(let ([table (make-level-table (hasheqv) 0 root)])
(for/list ([level (in-range (hash-count table))])
(hash-ref table level))))