-
Notifications
You must be signed in to change notification settings - Fork 1
/
124BTreeLevelOrderTraversal4.cs
101 lines (84 loc) · 2.61 KB
/
124BTreeLevelOrderTraversal4.cs
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
91
92
93
94
95
96
97
98
99
100
101
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace BTreeLevelOrderTraversal4
{
class TreeNode
{
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x)
{
val = x;
left = null;
right = null;
}
};
class BTreeLevelOrderTraversal4
{
static void Main(string[] args)
{
/*Latest update: July 23, 2015
* Test the code
*/
TreeNode n1 = new TreeNode(1);
n1.left = new TreeNode(2);
n1.right = new TreeNode(3);
n1.left.left = new TreeNode(4);
n1.left.right = new TreeNode(5);
n1.right.left = new TreeNode(6);
n1.right.right = new TreeNode(7);
IList<IList<int>> result3 = levelOrder(n1);
}
/*
* source code from blog:
* http://fisherlei.blogspot.ca/2013/01/leetcode-binary-tree-level-order.html
*
* convert from C++ to C#
* Julia's commment:
* 1. It is DFS algorithm
*/
public static IList<IList<int>> levelOrder(TreeNode root) {
IList<IList<int>> output = new List<IList<int>>();
if(root == null )
return output;
IList<int> oneLine = new List<int>();
int currentLevel = 1;
bool hasNextLevel = true;
while(hasNextLevel)
{
hasNextLevel = false;
levelTravel(root, currentLevel, ref hasNextLevel, oneLine);
List<int> l = new List<int>();
l.AddRange(oneLine);
output.Add(l);
oneLine.Clear();
currentLevel++;
}
return output;
}
public static void levelTravel(
TreeNode node,
int level,
ref bool hasNextLevel,
IList<int> result)
{
if(node == null) return;
if(level == 1)
{
result.Add(node.val);
if(node.left !=null || node.right !=null)
hasNextLevel = true;
return;
}
else
{
levelTravel(node.left, level-1, ref hasNextLevel, result);
levelTravel(node.right, level-1, ref hasNextLevel, result);
}
}
}
}