Given the
rootof a binary tree, return an array of the largest value in each row of the tree (0-indexed).Example 1:
Example 2:
Example 3:
Example 4:
Example 5:
Constraints:
- The number of the nodes in the tree will be in the range
[1, 104].-231 <= Node.val <= 231 - 1
Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
data Tree = Node Int Tree Tree | Nil deriving (Show, Read, Eq)
instance Ord Tree where
compare Nil Nil = EQ
compare Nil (Node _ _ _) = LT
compare (Node _ _ _) Nil = GT
compare (Node a _ _) (Node b _ _) = compare a b
largestValues :: Tree -> [Tree]
largestValues root = largestValues' [root] []
largestValues' :: [Tree] -> [Tree] -> [Tree]
largestValues' [] maxes = maxes
largestValues' [Nil] _ = []
largestValues' nodes maxes = largestValues' (add nodes) ((maximum nodes):maxes) where
add :: [Tree] -> [Tree]
add [Nil] = []
add [(Node val l r)] | l == Nil && r == Nil = []
| l == Nil = [r]
| r == Nil = [l]
| otherwise = [l, r]
add ns = foldr (\x acc -> add [x] ++ acc) [] ns
BFS Solution
Comments powered by Disqus.