FilesExpand file tree

 master

/

103_zigzagLevelOrder.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

88 lines (82 loc) · 2.36 KB

 master

/

103_zigzagLevelOrder.java

Copy path

Top

File metadata and controls

• Code
• Blame

88 lines (82 loc) · 2.36 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

82

83

84

85

86

87

88

/**

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode(int x) { val = x; }

* }

*/

public class Solution {

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {

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

if(root == null) return result;

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

queue.add(root);

int depth = 1;

int current = 1;

int next = 0;

List<Integer> list = new ArrayList<Integer>();

Stack<Integer> stack = new Stack<Integer>();

while(!queue.isEmpty()){

TreeNode temp = queue.remove();

if(depth%2==0){

stack.push(temp.val);

} else{

list.add(temp.val);

}

if(temp.left!=null){

queue.add(temp.left);

next++;

}

if(temp.right!=null){

queue.add(temp.right);

next++;

}

current--;

if(current == 0){

if(depth%2==0){

while(!stack.isEmpty()){

list.add(stack.pop());

}

stack = new Stack<Integer>();

}

result.add(list);

depth++;

current = next;

next = 0;

list = new ArrayList<Integer>();

}

}

return result;

}

}

/**

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode(int x) { val = x; }

* }

*/

public class Solution {

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {

List<List<Integer>> res = new ArrayList<List<Integer>>();

dfs(root, 0, res);

return res;

}

public void dfs(TreeNode root, int level, List<List<Integer>> res){

if(root == null) return;

if(level >= res.size()){ // here is >=!!!!!!

res.add(new LinkedList<Integer>());

}

if(level % 2 == 0){

res.get(level).add(root.val);

} else {

res.get(level).add(0, root.val);

}

dfs(root.left, level+1, res);

dfs(root.right, level+1, res);

}

}