Skip to content

Commit 31a78b4

Browse files
TonnyLTonnyL
committed
feat: 102. Binary Tree Level Order Traversal
1 parent 0061fd3 commit 31a78b4

14 files changed

Lines changed: 520 additions & 1 deletion

‎Golang/BinaryTreeLevelOrderTraversal/BinaryTreeLevelOrderTraversal.go‎

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
package BinaryTreeLevelOrderTraversal
2+
3+
//Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
4+
//
5+
//For example:
6+
//Given binary tree [3,9,20,null,null,15,7],
7+
//3
8+
/// \
9+
//9 20
10+
/// \
11+
//15 7
12+
//return its level order traversal as:
13+
//[
14+
//[3],
15+
//[9,20],
16+
//[15,7]
17+
//]
18+
//
19+
//Accepted.
20+
21+
type TreeNode struct {
22+
Val int
23+
Left *TreeNode
24+
Right *TreeNode
25+
}
26+
27+
func levelOrder(root *TreeNode) [][]int {
28+
lists := make([][]int, 0)
29+
helper(&lists, root, 0)
30+
return lists
31+
}
32+
33+
func helper(lists *[][]int, root *TreeNode, height int) {
34+
if root == nil {
35+
return
36+
}
37+
if height >= len(*lists) {
38+
*lists = append(*lists, make([]int, 0))
39+
}
40+
41+
(*lists)[height] = append((*lists)[height], root.Val)
42+
helper(lists, root.Left, height+1)
43+
helper(lists, root.Right, height+1)
44+
}

‎Golang/BinaryTreeLevelOrderTraversal/BinaryTreeLevelOrderTraversal_test.go‎

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
package BinaryTreeLevelOrderTraversal
2+
3+
import (
4+
"testing"
5+
"reflect"
6+
)
7+
8+
func TestLevelOrder(t *testing.T) {
9+
10+
if len(levelOrder(nil)) == 0 {
11+
t.Log("pass")
12+
} else {
13+
t.Error("failed")
14+
}
15+
16+
if reflect.DeepEqual(levelOrder(
17+
&TreeNode{
18+
Val: 1,
19+
}), [][]int{{1,},}) {
20+
t.Log("pass")
21+
} else {
22+
t.Error("failed")
23+
}
24+
25+
if reflect.DeepEqual(levelOrder(
26+
&TreeNode{
27+
Val: 3,
28+
Left: &TreeNode{
29+
Val: 9,
30+
},
31+
Right: &TreeNode{
32+
Val: 20,
33+
Left: &TreeNode{
34+
Val: 15,
35+
},
36+
Right: &TreeNode{
37+
Val: 7,
38+
},
39+
},
40+
}), [][]int{{3,}, {9, 20,}, {15, 7,},}) {
41+
t.Log("pass")
42+
} else {
43+
t.Error("failed")
44+
}
45+
46+
}

‎Java/src/BinaryTreeLevelOrderTraversal.java‎

Lines changed: 77 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,77 @@
1+
import java.util.ArrayList;
2+
import java.util.LinkedList;
3+
import java.util.List;
4+
5+
/**
6+
* Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
7+
* <p>
8+
* For example:
9+
* Given binary tree [3,9,20,null,null,15,7],
10+
* 3
11+
* / \
12+
* 9 20
13+
* /\
14+
* 15 7
15+
* return its level order traversal as:
16+
* [
17+
* [3],
18+
* [9,20],
19+
* [15,7]
20+
* ]
21+
* <p>
22+
* Accepted.
23+
*/
24+
25+
public class BinaryTreeLevelOrderTraversal {
26+
27+
public List<List<Integer>> levelOrder(TreeNode root) {
28+
List<List<Integer>> lists = new ArrayList<>();
29+
helper(lists, root, 0);
30+
return lists;
31+
}
32+
33+
private void helper(List<List<Integer>> res, TreeNode node, int height) {
34+
if (node == null) {
35+
return;
36+
}
37+
if (height >= res.size()) {
38+
res.add(new LinkedList<>());
39+
}
40+
res.get(height).add(node.val);
41+
helper(res, node.left, height + 1);
42+
helper(res, node.right, height + 1);
43+
}
44+
45+
public static class TreeNode {
46+
47+
int val;
48+
TreeNode left;
49+
TreeNode right;
50+
51+
TreeNode(int x) {
52+
val = x;
53+
}
54+
55+
@Override
56+
public boolean equals(Object obj) {
57+
if (obj instanceof TreeNode) {
58+
TreeNode node = (TreeNode) obj;
59+
if (this.val != node.val) {
60+
return false;
61+
}
62+
if (this.left == null) {
63+
if (this.right == null) {
64+
return node.left == null && node.right == null;
65+
}
66+
return this.right.equals(node.right);
67+
}
68+
if (this.right == null) {
69+
return node.right == null;
70+
}
71+
return this.left.equals(node.left) && this.right.equals(node.right);
72+
}
73+
return false;
74+
}
75+
}
76+
77+
}

‎Java/src/BinaryTreeLevelOrderTraversalTest.java‎

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
import org.junit.Assert;
2+
import org.junit.Test;
3+
4+
import java.util.Arrays;
5+
import java.util.Collections;
6+
7+
public class BinaryTreeLevelOrderTraversalTest {
8+
9+
@Test
10+
public void testLevelOrder() {
11+
BinaryTreeLevelOrderTraversal b = new BinaryTreeLevelOrderTraversal();
12+
13+
Assert.assertTrue(b.levelOrder(null).isEmpty());
14+
15+
BinaryTreeLevelOrderTraversal.TreeNode node0 = new BinaryTreeLevelOrderTraversal.TreeNode(1);
16+
Assert.assertEquals(b.levelOrder(node0), Collections.singletonList(Collections.singletonList(1)));
17+
18+
BinaryTreeLevelOrderTraversal.TreeNode node1 = new BinaryTreeLevelOrderTraversal.TreeNode(3);
19+
node1.left = new BinaryTreeLevelOrderTraversal.TreeNode(9);
20+
node1.right = new BinaryTreeLevelOrderTraversal.TreeNode(20);
21+
node1.right.left = new BinaryTreeLevelOrderTraversal.TreeNode(15);
22+
node1.right.right = new BinaryTreeLevelOrderTraversal.TreeNode(7);
23+
24+
Assert.assertEquals(b.levelOrder(node1), Arrays.asList(Collections.singletonList(3), Arrays.asList(9, 20), Arrays.asList(15, 7)));
25+
26+
}
27+
28+
}

‎JavaScript/src/BinaryTreeLevelOrderTraversal.js‎

Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
/**
2+
* Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
3+
*
4+
* For example:
5+
* Given binary tree [3,9,20,null,null,15,7],
6+
* 3
7+
* / \
8+
* 9 20
9+
* / \
10+
* 15 7
11+
* return its level order traversal as:
12+
* [
13+
* [3],
14+
* [9,20],
15+
* [15,7]
16+
* ]
17+
*/
18+
19+
/**
20+
* @param {TreeNode} root
21+
* @return {number[][]}
22+
*/
23+
let levelOrder = function (root) {
24+
let lists = [];
25+
helper(lists, root, 0);
26+
return lists;
27+
};
28+
29+
let helper = function (lists, root, height) {
30+
if (root === null) {
31+
return
32+
}
33+
if (height >= lists.length) {
34+
lists.push([]);
35+
}
36+
lists[height].push(root.val);
37+
helper(lists, root.left, height + 1);
38+
helper(lists, root.right, height + 1);
39+
};
40+
41+
function TreeNode(val) {
42+
this.val = val;
43+
this.left = this.right = null;
44+
}
45+
46+
if (levelOrder(null).length === 0) {
47+
console.log("pass")
48+
} else {
49+
console.error("failed")
50+
}
51+
52+
let node0 = new TreeNode(1);
53+
if (levelOrder(node0).length === 1
54+
&& levelOrder(node0)[0][0] === 1) {
55+
console.log("pass")
56+
} else {
57+
console.error("failed")
58+
}
59+
60+
let node1 = new TreeNode(3);
61+
node1.left = new TreeNode(9);
62+
node1.right = new TreeNode(20);
63+
node1.right.left = new TreeNode(15);
64+
node1.right.right = new TreeNode(7);
65+
if (levelOrder(node1).length === 3) {
66+
console.log("pass")
67+
} else {
68+
console.error("failed")
69+
}

‎Kotlin/src/BinaryTreeLevelOrderTraversal.kt‎

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
/**
2+
* Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
3+
*
4+
* For example:
5+
* Given binary tree [3,9,20,null,null,15,7],
6+
* 3
7+
* / \
8+
* 9 20
9+
* /\
10+
* 15 7
11+
* return its level order traversal as:
12+
* [
13+
* [3],
14+
* [9,20],
15+
* [15,7]
16+
* ]
17+
*
18+
* Accepted.
19+
*/
20+
21+
class BinaryTreeLevelOrderTraversal {
22+
23+
fun levelOrder(root: TreeNode?): List<List<Int>> {
24+
val lists = mutableListOf<MutableList<Int>>()
25+
helper(lists, root, 0)
26+
return lists
27+
}
28+
29+
private fun helper(res: MutableList<MutableList<Int>>, node: TreeNode?, height: Int) {
30+
if (node == null) {
31+
return
32+
}
33+
if (height >= res.size) {
34+
res.add(mutableListOf())
35+
}
36+
res[height].add(node.`val`)
37+
helper(res, node.left, height + 1)
38+
helper(res, node.right, height + 1)
39+
}
40+
41+
data class TreeNode(
42+
43+
var `val`: Int,
44+
var left: TreeNode? = null,
45+
var right: TreeNode? = null
46+
47+
)
48+
49+
}

‎Kotlin/src/BinaryTreeLevelOrderTraversalTest.kt‎

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
import org.junit.Assert
2+
import org.junit.Test
3+
4+
class BinaryTreeLevelOrderTraversalTest {
5+
6+
@Test
7+
fun testLevelOrder() {
8+
val b = BinaryTreeLevelOrderTraversal()
9+
10+
Assert.assertTrue(b.levelOrder(null).isEmpty())
11+
12+
val node0 = BinaryTreeLevelOrderTraversal.TreeNode(1)
13+
Assert.assertEquals(b.levelOrder(node0), listOf(listOf(1)))
14+
15+
val node1 = BinaryTreeLevelOrderTraversal.TreeNode(3).apply {
16+
left = BinaryTreeLevelOrderTraversal.TreeNode(9)
17+
right = BinaryTreeLevelOrderTraversal.TreeNode(20).apply {
18+
left = BinaryTreeLevelOrderTraversal.TreeNode(15)
19+
right = BinaryTreeLevelOrderTraversal.TreeNode(7)
20+
}
21+
}
22+
23+
Assert.assertEquals(b.levelOrder(node1), listOf(listOf(3), listOf(9, 20), listOf(15, 7)))
24+
}
25+
26+
}

‎Python/BinaryTreeLevelOrderTraversal.py‎

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
# Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
2+
#
3+
# For example:
4+
# Given binary tree [3,9,20,null,null,15,7],
5+
# 3
6+
# / \
7+
# 9 20
8+
# /\
9+
# 15 7
10+
# return its level order traversal as:
11+
# [
12+
# [3],
13+
# [9,20],
14+
# [15,7]
15+
# ]
16+
#
17+
# Python, Python3 all accepted.
18+
19+
20+
class BinaryTreeLevelOrderTraversal:
21+
def levelOrder(self, root):
22+
"""
23+
:type root: TreeNode
24+
:rtype: List[List[int]]
25+
"""
26+
lists = []
27+
self.helper(lists, root, 0)
28+
return lists
29+
30+
def helper(self, res, root, height):
31+
"""
32+
:param res: List[List[int]]
33+
:param root: TreeNode
34+
:param height: Int
35+
:return:
36+
"""
37+
if root is None:
38+
return
39+
if height >= len(res):
40+
res.append([])
41+
res[height].append(root.val)
42+
self.helper(res, root.left, height + 1)
43+
self.helper(res, root.right, height + 1)
44+
45+
46+
class TreeNode(object):
47+
def __init__(self, x):
48+
self.val = x
49+
self.left = None
50+
self.right = None

0 commit comments

Comments
 (0)