LeetCode-in-All
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.
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;
impl Solution {
pub fn level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
let mut q = VecDeque::new();
let mut ans: Vec<Vec<i32>> = Vec::new();
q.push_back(vec![root]);
while let Some(cur_level) = q.pop_front() {
let mut cur_level_vals = Vec::new();
let mut children = Vec::new();
for node_option in cur_level {
if let Some(node) = node_option {
cur_level_vals.push(node.borrow().val);
children.push(node.borrow().left.clone());
children.push(node.borrow().right.clone());
}
}
if cur_level_vals.len() > 0 {
ans.push(cur_level_vals);
q.push_back(children);
}
}
return ans;
}
}