FilesExpand file tree

 master

/

BinaryTreeLevelOrderTraversalII.java

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

66 lines (62 loc) · 1.48 KB

 master

/

BinaryTreeLevelOrderTraversalII.java

Top

File metadata and controls

• Code
• Blame

66 lines (62 loc) · 1.48 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

import java.util.ArrayList;

import java.util.LinkedList;

import java.util.Queue;

/**

* Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

*

* For example:

* Given binary tree {3,9,20,#,#,15,7},

* 3

* / \

* 9 20

* / \

* 15 7

* return its bottom-up level order traversal as:

* [

* [15,7]

* [9,20],

* [3],

* ]

* confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

*

*/

public class BinaryTreeLevelOrderTraversalII {

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

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

if (root == null)

return ret;

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

Queue<TreeNode> queue = new LinkedList<TreeNode>();

queue.add(root);

int currentLevel = 1;

int nextLevel = 0;

while (!queue.isEmpty()) {

TreeNode node = queue.remove();

level.add(node.val);

currentLevel--;

if (node.left != null) {

queue.add(node.left);

nextLevel++;

}

if (node.right != null) {

queue.add(node.right);

nextLevel++;

}

if (currentLevel == 0) {

ret.add(level);

level = new ArrayList<Integer>();

currentLevel = nextLevel;

nextLevel = 0;

}

}

int i = 0, j = ret.size() - 1;

while (i < j) {

ArrayList<Integer> tmp = ret.get(i);

ret.set(i, ret.get(j));

ret.set(j, tmp);

i++;

j--;

}

return ret;

}

}