FilesExpand file tree

 master

/

BinaryTreeLevelOrderTraversal.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

81 lines (68 loc) · 2.47 KB

 master

/

BinaryTreeLevelOrderTraversal.java

Copy path

Top

File metadata and controls

• Code
• Blame

81 lines (68 loc) · 2.47 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

/**

* Practiced on 11/28/2012

*

* Traverse binary tree in level order.

*

* ======================================

* 11/29/2012 update the method without using recursion.

* It is also possible to use DFS.

* See http://www.leetcode.com/2010/09/binary-tree-level-order-traversal-using_17.html

*/

package com.congli.leetcode;

import java.util.ArrayList;

import java.util.LinkedList;

public class BinaryTreeLevelOrderTraversal {

// 11/28/2012

public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {

ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();

if(root == null) return result;

ArrayList<TreeNode> listNode = new ArrayList<TreeNode>();

listNode.add(root);

helper(listNode, result);

return result;

}

private void helper(ArrayList<TreeNode> listNode, ArrayList<ArrayList<Integer>> result)

{

ArrayList<TreeNode> newListNode = new ArrayList<TreeNode>();

ArrayList<Integer> resultLayer = new ArrayList<Integer>();

for(TreeNode node : listNode)

{

resultLayer.add(node.val);

if(node.left != null)

newListNode.add(node.left);

if(node.right!= null)

newListNode.add(node.right);

}

result.add(resultLayer);

if(newListNode.size() != 0)

{

helper(newListNode, result);

}

}

//11/29/2012 implemented without using recursion.

public ArrayList<ArrayList<Integer>> levelOrderIterative(TreeNode root)

{

ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();

if(root == null) return result;

LinkedList<TreeNode> listUp = new LinkedList<TreeNode>();

LinkedList<TreeNode> listDown = new LinkedList<TreeNode>();

listUp.add(root);

while(listUp.size() != 0)

{

ArrayList<Integer> layerList = new ArrayList<Integer>();

while(listUp.size() != 0)

{

TreeNode temp = listUp.pollFirst();

if(temp.left != null)

listDown.addLast(temp.left);

if(temp.right != null)

listDown.addLast(temp.right);

layerList.add(temp.val);

}

result.add(layerList);

listUp = listDown;

listDown = new LinkedList<TreeNode>();

}

return result;

}

}