Java/BinaryTreeZigZagLevelTraversal.java at master · rjtsdl/Java · GitHub

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
import java.util.*;

public class BinaryTreeZigZagLevelTraversal {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

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

		List<List<Integer>> ret = new LinkedList<List<Integer>>();
		if(root ==  null) return ret;

		LinkedList<TreeNode> forward = new LinkedList<TreeNode>();
		LinkedList<TreeNode> backward = new LinkedList<TreeNode>();
		forward.add(root);
		boolean isForward = true;

		while(true)
		{
			if(isForward)
			{
				if(forward.isEmpty())
				{
					break;
				}
				backward.clear();
				LinkedList<Integer> temp = new LinkedList<Integer>();

				while(!forward.isEmpty())
				{
					TreeNode head = forward.pop();
					temp.add(head.val);
					if(head.left!= null)
					{
						backward.push(head.left);
					}
					if(head.right!= null)
					{
						backward.push(head.right);
					}
				}
				isForward = false;
				ret.add(temp);
			}
			else
			{
				if(backward.isEmpty())
				{
					break;
				}
				forward.clear();
				LinkedList<Integer> temp = new LinkedList<Integer>();

				while(!backward.isEmpty())
				{
					TreeNode head = backward.pop();
					temp.add(head.val);
					if(head.right!= null)
					{
						forward.push(head.right);
					}
					if(head.left!= null)
					{
						forward.push(head.left);
					}
				}
				isForward = true;
				ret.add(temp);
			}

		}

		return ret;

    }

	public class TreeNode {
		    int val;
	        TreeNode left;
	        TreeNode right;
	        TreeNode(int x) { val = x; }
	}

}