# Binary Tree Level Order Traversal is Here!
# 102. Binary Tree Level Order Traversal
LeetCode Problem Link (opens new window)
Given a binary tree, return its node values as they are encountered in level order (i.e., from left to right, level by level).
# Idea
We previously discussed binary tree depth-first traversal in three posts:
- Binary Tree: Preorder, Inorder and Postorder Recursive Traversal (opens new window)
- Binary Tree: Preorder, Inorder and Postorder Iterative Traversal (opens new window)
- Binary Tree: Unified Iterative Traversal Method (opens new window)
Now, let's introduce another method for traversing binary trees: level order traversal.
Level order traversal traverses a binary tree from top to bottom and left to right layer by layer. This method is distinct from those discussed earlier.
To achieve this, we need a queue as an auxiliary data structure, as a queue's FIFO (first in, first out) principle aligns with the logic of layer-by-layer traversal. In contrast, a stack's LIFO (last in, first out) principle is more suitable for simulating depth-first (recursive) traversal.
This level order traversal method aligns with breadth-first traversal in graph theory, albeit applied to trees.
The following animation demonstrates using a queue for breadth-first traversal of a binary tree:
This effectively implements level order left-to-right traversal of a binary tree.
Here is the code: This code can also serve as a template for binary tree level order traversal, making it possible to tackle ten problems at once.
C++ code:
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> que;
if (root != NULL) que.push(root);
vector<vector<int>> result;
while (!que.empty()) {
int size = que.size();
vector<int> vec;
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
vec.push_back(node->val);
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
result.push_back(vec);
}
return result;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Recursive Method
class Solution {
public:
void order(TreeNode* cur, vector<vector<int>>& result, int depth)
{
if (cur == nullptr) return;
if (result.size() == depth) result.push_back(vector<int>());
result[depth].push_back(cur->val);
order(cur->left, result, depth + 1);
order(cur->right, result, depth + 1);
}
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> result;
int depth = 0;
order(root, result, depth);
return result;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Other Language Versions
# Java:
// 102. Binary Tree Level Order Traversal
class Solution {
public List<List<Integer>> resList = new ArrayList<List<Integer>>();
public List<List<Integer>> levelOrder(TreeNode root) {
// checkFun01(root, 0);
checkFun02(root);
return resList;
}
// BFS -- Recursive Method
public void checkFun01(TreeNode node, Integer deep) {
if (node == null) return;
deep++;
if (resList.size() < deep) {
List<Integer> item = new ArrayList<>();
resList.add(item);
}
resList.get(deep - 1).add(node.val);
checkFun01(node.left, deep);
checkFun01(node.right, deep);
}
// BFS -- Iterative Method -- Using Queue
public void checkFun02(TreeNode node) {
if (node == null) return;
Queue<TreeNode> que = new LinkedList<>();
que.offer(node);
while (!que.isEmpty()) {
List<Integer> itemList = new ArrayList<>();
int len = que.size();
while (len > 0) {
TreeNode tmpNode = que.poll();
itemList.add(tmpNode.val);
if (tmpNode.left != null) que.offer(tmpNode.left);
if (tmpNode.right != null) que.offer(tmpNode.right);
len--;
}
resList.add(itemList);
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
# Python:
# Using Length Method
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
queue = collections.deque([root])
result = []
while queue:
level = []
for _ in range(len(queue)):
cur = queue.popleft()
level.append(cur.val)
if cur.left:
queue.append(cur.left)
if cur.right:
queue.append(cur.right)
result.append(level)
return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Recursive Method
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
levels = []
def traverse(node, level):
if not node:
return
if len(levels) == level:
levels.append([])
levels[level].append(node.val)
traverse(node.left, level + 1)
traverse(node.right, level + 1)
traverse(root, 0)
return levels
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Go:
/**
102. Binary Tree Recursive Traversal
*/
func levelOrder(root *TreeNode) [][]int {
arr := [][]int{}
depth := 0
var order func(root *TreeNode, depth int)
order = func(root *TreeNode, depth int) {
if root == nil {
return
}
if len(arr) == depth {
arr = append(arr, []int{})
}
arr[depth] = append(arr[depth], root.Val)
order(root.Left, depth+1)
order(root.Right, depth+1)
}
order(root, depth)
return arr
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
102. Binary Tree Level Order Traversal Using Container Package
*/
func levelOrder(root *TreeNode) [][]int {
res := [][]int{}
if root == nil {//Prevent null
return res
}
queue := list.New()
queue.PushBack(root)
var tmpArr []int
for queue.Len() > 0 {
length := queue.Len() // Save the length of the current layer, then process the current layer
for i := 0; i < length; i++ {
node := queue.Remove(queue.Front()).(*TreeNode) // Dequeue
if node.Left != nil {
queue.PushBack(node.Left)
}
if node.Right != nil {
queue.PushBack(node.Right)
}
tmpArr = append(tmpArr, node.Val) // Add the value to the current layer array
}
res = append(res, tmpArr) // Add to result set
tmpArr = []int{} // Clear the layer data
}
return res
}
/**
102. Binary Tree Level Order Traversal Using Slice
*/
func levelOrder(root *TreeNode) [][]int {
res := make([][]int, 0)
if root == nil {
return res
}
queue := make([]*TreeNode, 0)
queue = append(queue, root)
for len(queue) > 0 {
size := len(queue)
level := make([]int, 0)
for i := 0; i < size; i++ {
node := queue[0]
queue = queue[1:]
level = append(level, node.Val)
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
res = append(res, level)
}
return res
}
/**
102. Binary Tree Level Order Traversal: Using Slice to Simulate Queue
*/
func levelOrder(root *TreeNode) (res [][]int) {
if root == nil {
return
}
curLevel := []*TreeNode{root} // Store the current layer nodes
for len(curLevel) > 0 {
nextLevel := []*TreeNode{} // Prepare to generate the next layer through the current layer
vals := []int{}
for _, node := range curLevel {
vals = append(vals, node.Val) // Collect the values of the current layer
// Collect the nodes of the next layer
if node.Left != nil {
nextLevel = append(nextLevel, node.Left)
}
if node.Right != nil {
nextLevel = append(nextLevel, node.Right)
}
}
res = append(res, vals)
curLevel = nextLevel // Change the next layer to the current layer
}
return
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
# JavaScript:
var levelOrder = function(root) {
// Binary tree level order traversal
let res = [], queue = [];
queue.push(root);
if(root === null) {
return res;
}
while(queue.length !== 0) {
// Record the current layer node count
let length = queue.length;
// Store the node of each layer
let curLevel = [];
for(let i = 0;i < length; i++) {
let node = queue.shift();
curLevel.push(node.val);
// Store nodes of the next layer
node.left && queue.push(node.left);
node.right && queue.push(node.right);
}
// Add each layer's result to the result array
res.push(curLevel);
}
return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# TypeScript:
function levelOrder(root: TreeNode | null): number[][] {
let helperQueue: TreeNode[] = [];
let res: number[][] = [];
let tempArr: number[] = [];
if (root !== null) helperQueue.push(root);
let curNode: TreeNode;
while (helperQueue.length > 0) {
for (let i = 0, length = helperQueue.length; i < length; i++) {
curNode = helperQueue.shift()!;
tempArr.push(curNode.val);
if (curNode.left !== null) {
helperQueue.push(curNode.left);
}
if (curNode.right !== null) {
helperQueue.push(curNode.right);
}
}
res.push(tempArr);
tempArr = [];
}
return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Swift:
func levelOrder(_ root: TreeNode?) -> [[Int]] {
var result = [[Int]]()
guard let root = root else { return result }
var queue = [root]
while !queue.isEmpty {
let count = queue.count
var subarray = [Int]()
for _ in 0 ..< count {
let node = queue.removeFirst()
subarray.append(node.val)
if let node = node.left { queue.append(node) }
if let node = node.right { queue.append(node) }
}
result.append(subarray)
}
return result
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Scala:
// 102. Binary Tree Level Order Traversal
object Solution {
import scala.collection.mutable
def levelOrder(root: TreeNode): List[List[Int]] = {
val res = mutable.ListBuffer[List[Int]]()
if (root == null) return res.toList
val queue = mutable.Queue[TreeNode]() // Declare a queue
queue.enqueue(root) // Add root node to queue
while (!queue.isEmpty) {
val tmp = mutable.ListBuffer[Int]()
val len = queue.size // Save the length of the queue
for (i <- 0 until len) { // All nodes within the current level are added to the result
val curNode = queue.dequeue()
tmp.append(curNode.value)
if (curNode.left != null) queue.enqueue(curNode.left)
if (curNode.right != null) queue.enqueue(curNode.right)
}
res.append(tmp.toList)
}
res.toList
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Rust:
use std::cell::RefCell;
use std::rc::Rc;
use std::collections::VecDeque;
impl Solution {
pub fn level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
let mut res = vec![];
let mut queue = VecDeque::new();
if root.is_some() {
queue.push_back(root);
}
while !queue.is_empty() {
let mut temp = vec![];
for _ in 0..queue.len() {
let node = queue.pop_front().unwrap().unwrap();
temp.push(node.borrow().val);
if node.borrow().left.is_some() {
queue.push_back(node.borrow().left.clone());
}
if node.borrow().right.is_some() {
queue.push_back(node.borrow().right.clone());
}
}
res.push(temp);
}
res
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# C#
public IList<IList<int>> LevelOrder(TreeNode root)
{
var res = new List<IList<int>>();
var que = new Queue<TreeNode>();
if (root == null) return res;
que.Enqueue(root);
while (que.Count != 0)
{
var size = que.Count;
var vec = new List<int>();
for (int i = 0; i < size; i++)
{
var cur = que.Dequeue();
vec.Add(cur.val);
if (cur.left != null) que.Enqueue(cur.left);
if (cur.right != null) que.Enqueue(cur.right);
}
res.Add(vec);
}
return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
With the mastery of binary tree level order traversal, you can solve the following nine problems with only modifications in the template code (no more than two or three lines, promised!):
# 107. Binary Tree Level Order Traversal II
LeetCode Problem Link (opens new window)
Given a binary tree, return its node values in level order from bottom to top (i.e., from leaf nodes to root nodes, left to right).
# Idea
Compared to 102. Binary Tree Level Order Traversal, this problem requires reversing the result array at the end.
C++ code:
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
queue<TreeNode*> que;
if (root != NULL) que.push(root);
vector<vector<int>> result;
while (!que.empty()) {
int size = que.size();
vector<int> vec;
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
vec.push_back(node->val);
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
result.push_back(vec);
}
reverse(result.begin(), result.end()); // Reverse the array here
return result;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Other Language Versions
# Python：
class Solution:
"""Iterative method for Binary Tree Level Order Traversal II"""
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
queue = collections.deque([root])
result = []
while queue:
level = []
for _ in range(len(queue)):
cur = queue.popleft()
level.append(cur.val)
if cur.left:
queue.append(cur.left)
if cur.right:
queue.append(cur.right)
result.append(level)
return result[::-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# Java：
// 107. Binary Tree Level Order Traversal II
public class N0107 {
/**
* Method: Queue, Iterative.
* Perform level order traversal and then reverse the array.
*/
public List<List<Integer>> solution1(TreeNode root) {
List<List<Integer>> list = new ArrayList<>();
Deque<TreeNode> que = new LinkedList<>();
if (root == null) {
return list;
}
que.offerLast(root);
while (!que.isEmpty()) {
List<Integer> levelList = new ArrayList<>();
int levelSize = que.size();
for (int i = 0; i < levelSize; i++) {
TreeNode peek = que.peekFirst();
levelList.add(que.pollFirst().val);
if (peek.left != null) {
que.offerLast(peek.left);
}
if (peek.right != null) {
que.offerLast(peek.right);
}
}
list.add(levelList);
}
List<List<Integer>> result = new ArrayList<>();
for (int i = list.size() - 1; i >= 0; i-- ) {
result.add(list.get(i));
}
return result;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
* The logic and template are similar, with an optimized result collection method that doesn't require final reversal.
*/
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
// Using LinkedList allows for O(1) head insertion, thus meeting reverse order requirements without further reversal
LinkedList<List<Integer>> ans = new LinkedList<>();
Queue<TreeNode> q = new LinkedList<>();
if (root != null) q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
List<Integer> temp = new ArrayList<>();
for (int i = 0; i < size; i ++) {
TreeNode node = q.poll();
temp.add(node.val);
if (node.left != null) q.offer(node.left);
if (node.right != null) q.offer(node.right);
}
ans.addFirst(temp); // Prepend newly traversed level
}
return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# Go:
/**
107. Binary Tree Level Order Traversal II
*/
func levelOrderBottom(root *TreeNode) [][]int {
queue := list.New()
res := [][]int{}
if root == nil{
return res
}
queue.PushBack(root)
for queue.Len() > 0 {
length := queue.Len()
tmp := []int{}
for i := 0; i < length; i++ {
node := queue.Remove(queue.Front()).(*TreeNode)
if node.Left != nil {
queue.PushBack(node.Left)
}
if node.Right != nil {
queue.PushBack(node.Right)
}
tmp = append(tmp, node.Val)
}
res=append(res, tmp)
}
// Reverse the result
for i:=0; i<len(res)/2; i++ {
res[i], res[len(res)-i-1] = res[len(res)-i-1], res[i]
}
return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// Using slice as a queue
func levelOrderBottom(root *TreeNode) [][]int {
res := make([][]int, 0)
if root == nil {
return res
}
queue := make([]*TreeNode, 0)
queue = append(queue, root)
for len(queue) > 0 {
size := len(queue)
level := make([]int, 0)
for i := 0; i < size; i++ {
node := queue[0]
queue = queue[1:]
level = append(level, node.Val)
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
res = append(res, level)
}
l, r := 0, len(res)-1
for l < r {
res[l], res[r] = res[r], res[l]
l++
r--
}
return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# JavaScript:
var levelOrderBottom = function (root) {
let res = [],
queue = [];
queue.push(root);
while (queue.length && root !== null) {
// Store nodes for the current level
let length = queue.length;
let curLevel = [];
while (length--) {
let node = queue.shift();
curLevel.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
res.unshift(curLevel); // Prepend the current level to result, avoiding final reversal
}
return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# TypeScript:
function levelOrderBottom(root: TreeNode | null): number[][] {
let helperQueue: TreeNode[] = [];
let resArr: number[][] = [];
let tempArr: number[] = [];
let tempNode: TreeNode;
if (root !== null) helperQueue.push(root);
while (helperQueue.length > 0) {
for (let i = 0, length = helperQueue.length; i < length; i++) {
tempNode = helperQueue.shift()!;
tempArr.push(tempNode.val);
if (tempNode.left !== null) helperQueue.push(tempNode.left);
if (tempNode.right !== null) helperQueue.push(tempNode.right);
}
resArr.push(tempArr);
tempArr = [];
}
return resArr.reverse();
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Swift：
func levelOrderBottom(_ root: TreeNode?) -> [[Int]] {
var queue = [TreeNode]()
if let node = root { queue.append(node) }
var result = [[Int]]()
while !queue.isEmpty {
let count = queue.count
var subarray = [Int]()
for _ in 0 ..< count {
let node = queue.removeFirst()
subarray.append(node.val)
if let node = node.left { queue.append(node) }
if let node = node.right { queue.append(node)}
}
result.append(subarray)
}
return result.reversed()
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Scala:
// 107. Binary Tree Level Order Traversal II
object Solution {
import scala.collection.mutable
def levelOrderBottom(root: TreeNode): List[List[Int]] = {
val res = mutable.ListBuffer[List[Int]]()
if (root == null) return res.toList
val queue = mutable.Queue[TreeNode]()
queue.enqueue(root)
while (!queue.isEmpty) {
val tmp = mutable.ListBuffer[Int]()
val len = queue.size
for (i <- 0 until len) {
val curNode = queue.dequeue()
tmp.append(curNode.value)
if (curNode.left != null) queue.enqueue(curNode.left)
if (curNode.right != null) queue.enqueue(curNode.right)
}
res.append(tmp.toList)
}
res.reverse.toList // Reverse before returning
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Rust:
use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;
impl Solution {
pub fn level_order_bottom(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
let mut res = vec![];
let mut queue = VecDeque::new();
if root.is_some() {
queue.push_back(root);
}
while !queue.is_empty() {
let mut temp = vec![];
for _ in 0..queue.len() {
let node = queue.pop_front().unwrap().unwrap();
temp.push(node.borrow().val);
if node.borrow().left.is_some() {
queue.push_back(node.borrow().left.clone());
}
if node.borrow().right.is_some() {
queue.push_back(node.borrow().right.clone());
}
}
res.push(temp);
}
res.into_iter().rev().collect()
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# C#
public IList<IList<int>> LevelOrderBottom(TreeNode root)
{
var res = new List<IList<int>>();
var que = new Queue<TreeNode>();
if (root == null) return res;
que.Enqueue(root);
while (que.Count != 0)
{
var size = que.Count;
var vec = new List<int>();
for (int i = 0; i < size; i++)
{
var cur = que.Dequeue();
vec.Add(cur.val);
if (cur.left != null) que.Enqueue(cur.left);
if (cur.right != null) que.Enqueue(cur.right);
}
res.Add(vec);
}
res.Reverse();
return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 199. Binary Tree Right Side View
LeetCode Problem Link (opens new window)
Given a binary tree, imagine yourself standing on its right side and returning the values of the nodes you can see ordered from top to bottom.
# Idea
While performing a level order traversal, check if you are visiting the last element of the level, and if so, add it to the result array.
C++ code:
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
queue<TreeNode*> que;
if (root != NULL) que.push(root);
vector<int> result;
while (!que.empty()) {
int size = que.size();
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
if (i == (size - 1)) result.push_back(node->val); // Add the last element of each level to the result
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
}
return result;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Other Language Versions
# Python：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def rightSideView(self, root: TreeNode) -> List[int]:
if not root:
return []
queue = collections.deque([root])
right_view = []
while queue:
level_size = len(queue)
for i in range(level_size):
node = queue.popleft()
if i == level_size - 1:
right_view.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return right_view
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# Java:
// 199. Binary Tree Right Side View
public class N0199 {
/**
* Method: Queue, Iterative.
* Returns the last element of each level.
*/
public List<Integer> rightSideView(TreeNode root) {
List<Integer> list = new ArrayList<>();
Deque<TreeNode> que = new LinkedList<>();
if (root == null) {
return list;
}
que.offerLast(root);
while (!que.isEmpty()) {
int levelSize = que.size();
for (int i = 0; i < levelSize; i++) {
TreeNode poll = que.pollFirst();
if (poll.left != null) {
que.addLast(poll.left);
}
if (poll.right != null) {
que.addLast(poll.right);
}
if (i == levelSize - 1) {
list.add(poll.val);
}
}
}
return list;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# Go:
/**
199. Binary Tree Right Side View
*/
func rightSideView(root *TreeNode) []int {
if root == nil {
return nil
}
res := make([]int, 0)
queue := list.New()
queue.PushBack(root)
for queue.Len() > 0 {
length := queue.Len()
for i := 0; i < length; i++ {
node := queue.Remove(queue.Front()).(*TreeNode)
if node.Left != nil {
queue.PushBack(node.Left)
}
if node.Right != nil {
queue.PushBack(node.Right)
}
// Add the last node of each level to the result
if i == length-1 {
res = append(res, node.Val)
}
}
}
return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// Using slice as a queue
func rightSideView(root *TreeNode) []int {
res := make([]int, 0)
if root == nil {
return res
}
queue := make([]*TreeNode, 0)
queue = append(queue, root)
for len(queue) > 0 {
size := len(queue)
for i := 0; i < size; i++ {
node := queue[0]
queue = queue[1:]
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
if i == size-1 {
res = append(res, node.Val)
}
}
}
return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# JavaScript:
var rightSideView = function(root) {
// Binary tree right view, only need to store the last node of each level to res array
let res = [], queue = [];
queue.push(root);
while(queue.length && root!==null) {
// Record the number of nodes in the current level
let length = queue.length;
while(length--) {
let node = queue.shift();
// When the length is 0, it indicates the last node of the level
if(!length) {
res.push(node.val);
}
node.left && queue.push(node.left);
node.right && queue.push(node.right);
}
}
return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# TypeScript：
function rightSideView(root: TreeNode | null): number[] {
let helperQueue: TreeNode[] = [];
let resArr: number[] = [];
let tempNode: TreeNode;
if (root !== null) helperQueue.push(root);
while (helperQueue.length > 0) {
for (let i = 0, length = helperQueue.length; i < length; i++) {
tempNode = helperQueue.shift()!;
if (i === length - 1) resArr.push(tempNode.val);
if (tempNode.left !== null) helperQueue.push(tempNode.left);
if (tempNode.right !== null) helperQueue.push(tempNode.right);
}
}
return resArr;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Swift：
func rightSideView(_ root: TreeNode?) -> [Int] {
var queue = [TreeNode]()
if let node = root { queue.append(node) }
var result = [Int]()
while !queue.isEmpty {
let count = queue.count
for i in 0 ..< count {
let node = queue.removeFirst()
if i == count - 1 { result.append(node.val) }
if let node = node.left { queue.append(node) }
if let node = node.right { queue.append(node) }
}
}
return result
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Scala:
// 199. Binary Tree Right Side View
object Solution {
import scala.collection.mutable
def rightSideView(root: TreeNode): List[Int] = {
val res = mutable.ListBuffer[Int]()
if (root == null) return res.toList
val queue = mutable.Queue[TreeNode]()
queue.enqueue(root)
while (!queue.isEmpty) {
val len = queue.size
var curNode: TreeNode = null
for (i <- 0 until len) {
curNode = queue.dequeue()
if (curNode.left != null) queue.enqueue(curNode.left)
if (curNode.right != null) queue.enqueue(curNode.right)
}
res.append(curNode.value) // Add the last node value of the layer to the result set
}
res.toList
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Rust:
use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;
impl Solution {
pub fn right_side_view(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
let mut res = vec![];
let mut queue = VecDeque::new();
if root.is_some() {
queue.push_back(root);
}
while !queue.is_empty() {
let len = queue.len();
for i in 0..len {
let node = queue.pop_front().unwrap().unwrap();
if i == len - 1 {
res.push(node.borrow().val);
}
if node.borrow().left.is_some() {
queue.push_back(node.borrow().left.clone());
}
if node.borrow().right.is_some() {
queue.push_back(node.borrow().right.clone());
}
}
}
res
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# C#:
public class Solution
{
public IList<int> RightSideView(TreeNode root)
{
var result = new List<int>();
Queue<TreeNode> queue = new();
if (root != null)
{
queue.Enqueue(root);
}
while (queue.Count > 0)
{
int count = queue.Count;
int lastValue = count - 1;
for (int i = 0; i < count; i++)
{
var currentNode = queue.Dequeue();
if (i == lastValue)
{
result.Add(currentNode.val);
}
if (currentNode.left != null) queue.Enqueue(currentNode.left);
if (currentNode.right != null) queue.Enqueue(currentNode.right);
}
}
return result;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# 637. Average of Levels in Binary Tree
LeetCode Problem Link (opens new window)
Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.
# Idea
For this problem, compute the sum of each level during level order traversal and then take the average.
C++ code:
class Solution {
public:
vector<double> averageOfLevels(TreeNode* root) {
queue<TreeNode*> que;
if (root != NULL) que.push(root);
vector<double> result;
while (!que.empty()) {
int size = que.size();
double sum = 0; // Sum of each level
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
sum += node->val;
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
result.push_back(sum / size); // Push the average of each level into the result set
}
return result;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Other Language Versions
# Python：
class Solution:
"""Iterative solution for average of levels in binary tree"""
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def averageOfLevels(self, root: TreeNode) -> List[float]:
if not root:
return []
queue = collections.deque([root])
averages = []
while queue:
size = len(queue)
level_sum = 0
for i in range(size):
node = queue.popleft()
level_sum += node.val
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
averages.append(level_sum / size)
return averages
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# Java:
// 637. Average of Levels in Binary Tree
public class N0637 {
/**
* Method: Queue, Iterative.
*/
public List<Double> averageOfLevels(TreeNode root) {
List<Double> list = new ArrayList<>();
Deque<TreeNode> que = new LinkedList<>();
if (root == null) {
return list;
}
que.offerLast(root);
while (!que.isEmpty()) {
int levelSize = que.size();
double levelSum = 0.0;
for (int i = 0; i < levelSize; i++) {
TreeNode poll = que.pollFirst();
levelSum += poll.val;
if (poll.left != null) {
que.addLast(poll.left);
}
if (poll.right != null) {
que.addLast(poll.right);
}
}
list.add(levelSum / levelSize);
}
return list;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# Go:
/**
637. Average of Levels in Binary Tree
*/
func averageOfLevels(root *TreeNode) []float64 {
if root == nil {
return nil
}
res := make([]float64, 0)
queue := list.New()
queue.PushBack(root)
var sum int
for queue.Len() > 0 {
length := queue.Len()
for i := 0; i < length; i++ {
node := queue.Remove(queue.Front()).(*TreeNode)
if node.Left != nil {
queue.PushBack(node.Left)
}
if node.Right != nil {
queue.PushBack(node.Right)
}
sum += node.Val
}
res = append(res, float64(sum)/float64(length))
sum = 0
}
return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// Using slice as a queue
func averageOfLevels(root *TreeNode) []float64 {
res := make([]float64, 0)
if root == nil {
return res
}
queue := make([]*TreeNode, 0)
queue = append(queue, root)
for len(queue) > 0 {
size := len(queue)
sum := 0
for i := 0; i < size; i++ {
node := queue[0]
queue = queue[1:]
sum += node.Val
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
res = append(res, float64(sum)/float64(size))
}
return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# JavaScript：
var averageOfLevels = function(root) {
let res = [],
queue = [];
queue.push(root);
while (queue.length) {
// Number of nodes at current level
let lengthLevel = queue.length,
len = queue.length,
// Sum records the sum of the current level
sum = 0;
while (lengthLevel--) {
const node = queue.shift();
sum += node.val;
// Queue stores nodes of the next level
node.left && queue.push(node.left);
node.right && queue.push(node.right);
}
// Calculate the average
res.push(sum / len);
}
return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# TypeScript：
function averageOfLevels(root: TreeNode | null): number[] {
let helperQueue: TreeNode[] = [];
let resArr: number[] = [];
let total: number = 0;
let tempNode: TreeNode;
if (root !== null) helperQueue.push(root);
while (helperQueue.length > 0) {
let length = helperQueue.length;
for (let i = 0; i < length; i++) {
tempNode = helperQueue.shift()!;
total += tempNode.val;
if (tempNode.left) helperQueue.push(tempNode.left);
if (tempNode.right) helperQueue.push(tempNode.right);
}
resArr.push(total / length);
total = 0;
}
return resArr;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Swift：
func averageOfLevels(_ root: TreeNode?) -> [Double] {
var queue = [TreeNode]()
if let node = root { queue.append(node) }
var result = [Double]()
while !queue.isEmpty {
let count = queue.count
var sum = 0
for _ in 0 ..< count {
let node = queue.removeFirst()
sum += node.val
if let node = node.left { queue.append(node) }
if let node = node.right { queue.append(node) }
}
result.append(Double(sum) / Double(count))
}
return result
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Scala:
// 637. Average of Levels in Binary Tree
object Solution {
import scala.collection.mutable
def averageOfLevels(root: TreeNode): Array[Double] = {
val res = mutable.ArrayBuffer[Double]()
val queue = mutable.Queue[TreeNode]()
queue.enqueue(root)
while (!queue.isEmpty) {
var sum = 0.0
var len = queue.size
for (i <- 0 until len) {
var curNode = queue.dequeue()
sum += curNode.value
if (curNode.left != null) queue.enqueue(curNode.left)
if (curNode.right != null) queue.enqueue(curNode.right)
}
res.append(sum / len)
}
res.toArray
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Rust:
use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;
impl Solution {
pub fn average_of_levels(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<f64> {
let mut res = vec![];
let mut queue = VecDeque::new();
if root.is_some() {
queue.push_back(root);
}
while !queue.is_empty() {
let len = queue.len();
let mut sum = 0;
for _ in 0..len {
let node = queue.pop_front().unwrap().unwrap();
sum += node.borrow().val;
if node.borrow().left.is_some() {
queue.push_back(node.borrow().left.clone());
}
if node.borrow().right.is_some() {
queue.push_back(node.borrow().right.clone());
}
}
res.push((sum as f64) / len as f64);
}
res
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# C#:
public class Solution {
public IList<double> AverageOfLevels(TreeNode root) {
var result= new List<double>();
Queue<TreeNode> queue = new();
if(root !=null) queue.Enqueue(root);
while (queue.Count > 0)
{
int count = queue.Count;
double value=0;
for (int i = 0; i < count; i++)
{
var curentNode=queue.Dequeue();
value += curentNode.val;
if (curentNode.left!=null) queue.Enqueue(curentNode.left);
if (curentNode.right!=null) queue.Enqueue(curentNode.right);
}
result.Add(value/count);
}
return result;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 429. N-ary Tree Level Order Traversal
LeetCode Problem Link (opens new window)
Given an N-ary tree, return the level order traversal of its nodes' values (i.e., from left to right, level by level).
For example, given a 3-ary tree:
Return its level order traversal:
[
[1],
[3,2,4],
[5,6]
]
1
2
3
4
5
2
3
4
5
# Idea
This problem remains a template problem, just that a node has multiple children now.
C++ code:
class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
queue<Node*> que;
if (root != NULL) que.push(root);
vector<vector<int>> result;
while (!que.empty()) {
int size = que.size();
vector<int> vec;
for (int i = 0; i < size; i++) {
Node* node = que.front();
que.pop();
vec.push_back(node->val);
for (int i = 0; i < node->children.size(); i++) { // Add the children of the node to the queue
if (node->children[i]) que.push(node->children[i]);
}
}
result.push_back(vec);
}
return result;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Other Language Versions
# Python：
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
class Solution:
def levelOrder(self, root: 'Node') -> List[List[int]]:
if not root:
return []
result = []
queue = collections.deque([root])
while queue:
level_size = len(queue)
level = []
for _ in range(level_size):
node = queue.popleft()
level.append(node.val)
for child in node.children:
queue.append(child)
result.append(level)
return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# LeetCode 429. N-ary Tree Level Order Traversal
# Recursive Method
class Solution:
def levelOrder(self, root: 'Node') -> List[List[int]]:
if not root: return []
result=[]
def traversal(root,depth):
if len(result)==depth:result.append([])
result[depth].append(root.val)
if root.children:
for i in range(len(root.children)):traversal(root.children[i],depth+1)
traversal(root,0)
return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
# Java:
// 429. N-ary Tree Level Order Traversal
public class N0429 {
/**
* Method 1: Queue, Iterative.
*/
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> list = new ArrayList<>();
Deque<Node> que = new LinkedList<>();
if (root == null) {
return list;
}
que.offerLast(root);
while (!que.isEmpty()) {
int levelSize = que.size();
List<Integer> levelList = new ArrayList<>();
for (int i = 0; i < levelSize; i++) {
Node poll = que.pollFirst();
levelList.add(poll.val);
List<Node> children = poll.children;
if (children == null || children.size() == 0) {
continue;
}
for (Node child : children) {
if (child != null) {
que.offerLast(child);
}
}
}
list.add(levelList);
}
return list;
}
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
# Go:
/**
429. N-ary Tree Level Order Traversal
*/
func levelOrder(root *Node) [][]int {
queue := list.New()
res := [][]int{}
if root == nil{
return res
}
queue.PushBack(root)
for queue.Len() > 0 {
length := queue.Len()
var tmp []int
for T := 0; T < length; T++ {
myNode := queue.Remove(queue.Front()).(*Node)
tmp = append(tmp, myNode.Val)
for i := 0; i < len(myNode.Children); i++ {
queue.PushBack(myNode.Children[i])
}
}
res = append(res, tmp)
}
return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// Using slice as a queue
func levelOrder(root *Node) [][]int {
res := make([][]int, 0)
if root == nil {
return res
}
queue := make([]*Node, 0)
queue = append(queue, root)
for len(queue) > 0 {
size := len(queue)
level := make([]int, 0)
for i := 0; i < size; i++ {
node := queue[0]
queue = queue[1:]
level = append(level, node.Val)
if len(node.Children) > 0 {
queue = append(queue, node.Children...)
}
}
res = append(res, level)
}
return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# JavaScript：
var levelOrder = function(root) {
// Each layer may have more than two nodes, so no longer use node.left node.right
let res = [], queue = [];
queue.push(root);
while(queue.length && root!==null) {
// Record the number of nodes in the current level as before
let length = queue.length;
// Store each layer node, similar as binary tree
let curLevel = [];
while(length--) {
let node = queue.shift();
curLevel.push(node.val);
// Instead of node.left node.right, iterate over node.children
for(let item of node.children){
item && queue.push(item);
}
}
res.push(curLevel);
}
return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# TypeScript:
function levelOrder(root: Node | null): number[][] {
let helperQueue: Node[] = [];
let resArr: number[][] = [];
let tempArr: number[] = [];
if (root !== null) helperQueue.push(root);
let curNode: Node;
while (helperQueue.length > 0) {
for (let i = 0, length = helperQueue.length; i < length; i++) {
curNode = helperQueue.shift()!;
tempArr.push(curNode.val);
helperQueue.push(...curNode.children);
}
resArr.push(tempArr);
tempArr = [];
}
return resArr;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Swift：
func levelOrder(_ root: Node?) -> [[Int]] {
var queue = [Node]()
if let node = root { queue.append(node) }
var result = [[Int]]()
while !queue.isEmpty {
let count = queue.count
var subarray = [Int]()
for _ in 0 ..< count {
// Current layer
let node = queue.removeFirst()
subarray.append(node.val)
// Next layer
for node in node.children { queue.append(node) }
}
result.append(subarray)
}
return result
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Scala:
// 429. N-ary Tree Level Order Traversal
object Solution {
import scala.collection.mutable
def levelOrder(root: Node): List[List[Int]] = {
val res = mutable.ListBuffer[List[Int]]()
if (root == null) return res.toList
val queue = mutable.Queue[Node]()
queue.enqueue(root)
while (!queue.isEmpty) {
val tmp = mutable.ListBuffer[Int]()
val len = queue.size
for (i <- 0 until len) {
val curNode = queue.dequeue()
tmp.append(curNode.value)
for (child <- curNode.children) {
queue.enqueue(child)
}
}
res.append(tmp.toList)
}
res.toList
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Rust:
pub struct Solution;
#[derive(Debug, PartialEq, Eq)]
pub struct Node {
pub val: i32,
pub children: Vec<Option<Rc<RefCell<Node>>>>,
}
impl Node {
#[inline]
pub fn new(val: i32) -> Node {
Node {
val,
children: vec![],
}
}
}
use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;
impl Solution {
pub fn level_order(root: Option<Rc<RefCell<Node>>>) -> Vec<Vec<i32>> {
let mut res = vec![];
let mut queue = VecDeque::new();
if root.is_some() {
queue.push_back(root);
}
while !queue.is_empty() {
let mut temp = vec![];
for _ in 0..queue.len() {
let node = queue.pop_front().unwrap().unwrap();
temp.push(node.borrow().val);
if !node.borrow().children.is_empty() {
for n in node.borrow().children.clone() {
queue.push_back(n);
}
}
}
res.push(temp)
}
res
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# 515. Find Largest Value in Each Tree Row
LeetCode Problem Link (opens new window)
You need to find the largest value in each row of a binary tree.
# Idea
Perform a level order traversal and find the maximum value of each level.
C++ code:
class Solution {
public:
vector<int> largestValues(TreeNode* root) {
queue<TreeNode*> que;
if (root != NULL) que.push(root);
vector<int> result;
while (!que.empty()) {
int size = que.size();
int maxValue = INT_MIN; // Max value of each level
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
maxValue = node->val > maxValue ? node->val : maxValue;
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
result.push_back(maxValue); // Add the max value into the result
}
return result;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Other Language Versions
# Python：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def largestValues(self, root: TreeNode) -> List[int]:
if not root:
return []
result = []
queue = collections.deque([root])
while queue:
level_size = len(queue)
max_val = float('-inf')
for _ in range(level_size):
node = queue.popleft()
max_val = max(max_val, node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(max_val)
return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# Java：
class Solution {
public List<Integer> largestValues(TreeNode root) {
if(root == null){
return Collections.emptyList();
}
List<Integer> result = new ArrayList();
Queue<TreeNode> queue = new LinkedList();
queue.offer(root);
while(!queue.isEmpty()){
int max = Integer.MIN_VALUE;
for(int i = queue.size(); i > 0; i--){
TreeNode node = queue.poll();
max = Math.max(max, node.val);
if(node.left != null) queue.offer(node.left);
if(node.right != null) queue.offer(node.right);
}
result.add(max);
}
return result;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Go:
/**
515. Find Largest Value in Each Tree Row
*/
func largestValues(root *TreeNode) []int {
if root == nil {
return nil
}
queue := list.New()
queue.PushBack(root)
ans := make([]int, 0)
temp := math.MinInt64
for queue.Len() > 0 {
length := queue.Len()
for i := 0; i < length; i++ {
node := queue.Remove(queue.Front()).(*TreeNode)
temp = max(temp, node.Val)
if node.Left != nil {
queue.PushBack(node.Left)
}
if node.Right != nil {
queue.PushBack(node.Right)
}
}
ans = append(ans, temp)
temp = math.MinInt64
}
return ans
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// Using slice as a queue
func largestValues(root *TreeNode) []int {
res := make([]int, 0)
if root == nil {
return res
}
queue := make([]*TreeNode, 0)
queue = append(queue, root)
for len(queue) > 0 {
size := len(queue)
maxValue := math.MinInt64
for i := 0; i < size; i++ {
node := queue[0]
queue = queue[1:]
if node.Val > maxValue {
maxValue = node.Val
}
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
res = append(res, maxValue)
}
return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# JavaScript：
var largestValues = function (root) {
let res = [],
queue = [];
queue.push(root);
if (root === null) {
return res;
}
while (queue.length) {
let lengthLevel = queue.length,
// Initialize with negative infinity
max = -Infinity;
while (lengthLevel--) {
const node = queue.shift();
// Find the maximum value in the current level
max = Math.max(max, node.val);
// Find nodes of the next level
node.left && queue.push(node.left);
node.right && queue.push(node.right);
}
res.push(max);
}
return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# TypeScript:
function largestValues(root: TreeNode | null): number[] {
let helperQueue: TreeNode[] = [];
let resArr: number[] = [];
let tempNode: TreeNode;
let max: number = 0;
if (root !== null) helperQueue.push(root);
while (helperQueue.length > 0) {
for (let i = 0, length = helperQueue.length; i < length; i++) {
tempNode = helperQueue.shift()!;
if (i === 0) {
max = tempNode.val;
} else {
max = max > tempNode.val ? max : tempNode.val;
}
if (tempNode.left) helperQueue.push(tempNode.left);
if (tempNode.right) helperQueue.push(tempNode.right);
}
resArr.push(max);
}
return resArr;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Swift：
func largestValues(_ root: TreeNode?) -> [Int] {
var queue = [TreeNode]()
if let node = root { queue.append(node) }
var result = [Int]()
while !queue.isEmpty {
let count = queue.count
var max = queue[0].val
for _ in 0 ..< count {
let node = queue.removeFirst()
if node.val > max { max = node.val }
if let node = node.left { queue.append(node) }
if let node = node.right { queue.append(node) }
}
result.append(max)
}
return result
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Scala:
// 515. Find Largest Value in Each Tree Row
object Solution {
import scala.collection.mutable
def largestValues(root: TreeNode): List[Int] = {
val res = mutable.ListBuffer[Int]()
if (root == null) return res.toList
val queue = mutable.Queue[TreeNode]()
queue.enqueue(root)
while (!queue.isEmpty) {
var max = Int.MinValue
val len = queue.size
for (i <- 0 until len) {
val curNode = queue.dequeue()
max = math.max(max, curNode.value)
if (curNode.left != null) queue.enqueue(curNode.left)
if (curNode.right != null) queue.enqueue(curNode.right)
}
res.append(max)
}
res.toList
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Rust:
use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;
impl Solution {
pub fn largest_values(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
let mut res = vec![];
let mut queue = VecDeque::new();
if root.is_some() {
queue.push_back(root);
}
while !queue.is_empty() {
let mut max = i32::MIN;
for _ in 0..queue.len() {
let node = queue.pop_front().unwrap().unwrap();
max = max.max(node.borrow().val);
if node.borrow().left.is_some() {
queue.push_back(node.borrow().left.clone());
}
if node.borrow().right.is_some() {
queue.push_back(node.borrow().right.clone());
}
}
res.push(max);
}
res
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# 116. Populating Next Right Pointers in Each Node
LeetCode Problem Link (opens new window)
You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree is defined as follows:
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
1
2
3
4
5
6
2
3
4
5
6
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
# Idea
For this problem, perform a level order traversal, recording the head of the current layer. For each node, make the previous node point to the current node.
C++ code:
class Solution {
public:
Node* connect(Node* root) {
queue<Node*> que;
if (root != NULL) que.push(root);
while (!que.empty()) {
int size = que.size();
Node* nodePre;
Node* node;
for (int i = 0; i < size; i++) {
if (i == 0) {
nodePre = que.front(); // Head of the layer
que.pop();
node = nodePre;
} else {
node = que.front();
que.pop();
nodePre->next = node; // Previous node points to the current node
nodePre = nodePre->next;
}
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
nodePre->next = NULL; // Last node of the layer points to NULL
}
return root;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# Other Language Versions
# Java：
class Solution {
public Node connect(Node root) {
Queue<Node> tmpQueue = new LinkedList<Node>();
if (root != null) tmpQueue.add(root);
while (tmpQueue.size() != 0){
int size = tmpQueue.size();
Node cur = tmpQueue.poll();
if (cur.left != null) tmpQueue.add(cur.left);
if (cur.right != null) tmpQueue.add(cur.right);
for (int index = 1; index < size; index++){
Node next = tmpQueue.poll();
if (next.left != null) tmpQueue.add(next.left);
if (next.right != null) tmpQueue.add(next.right);
cur.next = next;
cur = next;
}
}
return root;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# Python：
"""
# Definition for a Node.
class Node:
def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
self.val = val
self.left = left
self.right = right
self.next = next
"""
class Solution:
def connect(self, root: 'Node') -> 'Node':
if not root:
return root
queue = collections.deque([root])
while queue:
level_size = len(queue)
prev = None
for i in range(level_size):
node = queue.popleft()
if prev:
prev.next = node
prev = node
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return root
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# Go:
/**
116. Connect Each Node's Next Right Pointer
117. Connect Each Node's Next Right Pointer II
*/
func connect(root *Node) *Node {
if root == nil {
return root
}
queue := list.New()
queue.PushBack(root)
tmpArr := make([]*Node, 0)
for queue.Len() > 0 {
length := queue.Len()
for i := 0; i < length; i++ {
node := queue.Remove(queue.Front()).(*Node)
if node.Left != nil {
queue.PushBack(node.Left)
}
if node.Right != nil {
queue.PushBack(node.Right)
}
tmpArr = append(tmpArr, node)
}
if len(tmpArr) > 1 {
for i := 0; i < len(tmpArr)-1; i++ {
tmpArr[i].Next = tmpArr[i+1]
}
}
tmpArr = []*Node{}
}
return root
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// Using slice as a queue
func connect(root *Node) *Node {
if root == nil {
return root
}
queue := make([]*Node, 0)
queue = append(queue, root)
for len(queue) > 0 {
size := len(queue)
for i := 0; i < size; i++ {
node := queue[i]
if i != size - 1 {
queue[i].Next = queue[i+1]
}
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
queue = queue[size:]
}
return root
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# JavaScript:
/**
* // Definition for a Node.
* function Node(val, left, right, next) {
* this.val = val === undefined ? null : val;
* this.left = left === undefined ? null : left;
* this.right = right === undefined ? null : right;
* this.next = next === undefined ? null : next;
* };
*/
/**
* @param {Node} root
* @return {Node}
*/
var connect = function(root) {
if (root === null) return root;
let queue = [root];
while (queue.length) {
let n = queue.length;
for (let i = 0; i < n; i++) {
let node = queue.shift();
if (i < n-1) {
node.next = queue[0];
}
node.left && queue.push(node.left);
node.right && queue.push(node.right);
}
}
return root;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# TypeScript:
function connect(root: Node | null): Node | null {
let helperQueue: Node[] = [];
let preNode: Node, curNode: Node;
if (root !== null) helperQueue.push(root);
while (helperQueue.length > 0) {
for (let i = 0, length = helperQueue.length; i < length; i++) {
if (i === 0) {
preNode = helperQueue.shift()!;
} else {
curNode = helperQueue.shift()!;
preNode.next = curNode;
preNode = curNode;
}
if (preNode.left) helperQueue.push(preNode.left);
if (preNode.right) helperQueue.push(preNode.right);
}
preNode.next = null;
}
return root;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Swift：
func connect(_ root: Node?) -> Node? {
var queue = [Node]()
if let node = root { queue.append(node) }
while !queue.isEmpty {
let count = queue.count
var current, previous: Node!
for i in 0 ..< count {
if i == 0 {
previous = queue.removeFirst()
current = previous
} else {
current = queue.removeFirst()
previous.next = current
previous = current
}
if let node = current.left { queue.append(node) }
if let node = current.right { queue.append(node) }
}
previous.next = nil
}
return root
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Scala:
// 116. Populating Next Right Pointers in Each Node
object Solution {
import scala.collection.mutable
def connect(root: Node): Node = {
if (root == null) return root
val queue = mutable.Queue[Node]()
queue.enqueue(root)
while (!queue.isEmpty) {
val len = queue.size
val tmp = mutable.ListBuffer[Node]()
for (i <- 0 until len) {
val curNode = queue.dequeue()
tmp.append(curNode)
if (curNode.left != null) queue.enqueue(curNode.left)
if (curNode.right != null) queue.enqueue(curNode.right)
}
for (i <- 0 until tmp.size - 1) {
tmp(i).next = tmp(i + 1)
}
tmp(tmp.size-1).next = null
}
root
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 117. Populating Next Right Pointers in Each Node II
LeetCode Problem Link (opens new window)
# Idea
This problem is similar to 116. Populating Next Right Pointers in Each Node in that it operates on a binary tree. In practice, the code and logic remain unchanged.
C++ code:
class Solution {
public:
Node* connect(Node* root) {
queue<Node*> que;
if (root != NULL) que.push(root);
while (!que.empty()) {
int size = que.size();
Node* nodePre;
Node* node;
for (int i = 0; i < size; i++) {
if (i == 0) {
nodePre = que.front(); // Head of the layer
que.pop();
node = nodePre;
} else {
node = que.front();
que.pop();
nodePre->next = node; // Previous node points to the current node
nodePre = nodePre->next;
}
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
nodePre->next = NULL; // Last node of the layer points to NULL
}
return root;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# Other Language Versions
# Java：
// Binary tree level order traversal
class Solution {
public Node connect(Node root) {
Queue<Node> queue = new LinkedList<>();
if (root != null) {
queue.add(root);
}
while (!queue.isEmpty()) {
int size = queue.size();
Node node = null;
Node nodePre = null;
for (int i = 0; i < size; i++) {
if (i == 0) {
nodePre = queue.poll(); // First node of the layer
node = nodePre;
} else {
node = queue.poll();
nodePre.next = node; // Previous node next points to the current node
nodePre = nodePre.next;
}
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
nodePre.next = null; // Last node of the layer next points to null
}
return root;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# Python：
# Level order traversal solution
"""
# Definition for a Node.
class Node:
def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
self.val = val
self.left = left
self.right = right
self.next = next
"""
class Solution:
def connect(self, root: 'Node') -> 'Node':
if not root:
return root
queue = collections.deque([root])
while queue:
level_size = len(queue)
prev = None
for i in range(level_size):
node = queue.popleft()
if prev:
prev.next = node
prev = node
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return root
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# Go:
/**
116. Connect Each Node's Next Right Pointer
117. Connect Each Node's Next Right Pointer II
*/
func connect(root *Node) *Node {
if root == nil {
return root
}
queue := list.New()
queue.PushBack(root)
tmpArr := make([]*Node, 0)
for queue.Len() > 0 {
length := queue.Len()
for i := 0;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Copyright © 2025 keetcoder