data-structures/src/com/leetcode/problems/medium/ZigZagLevelOrderTraversal.java at master · neerajjain92/data-structures · 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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
package com.leetcode.problems.medium;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Given binary tree [3,9,20,null,null,15,7],
 * 3
 * / \
 * 9  20
 * /  \
 * 15   7
 *
 * @author neeraj on 13/10/19
 * Copyright (c) 2019, data-structures.
 * All rights reserved.
 */
@SuppressWarnings("DuplicatedCode")
public class ZigZagLevelOrderTraversal {

    public static void main(String[] args) {
        TreeNode zigZagRoot = new TreeNode(3);
        zigZagRoot.left = new TreeNode(9);
        zigZagRoot.right = new TreeNode(20);
        zigZagRoot.right.left = new TreeNode(15);
        zigZagRoot.right.right = new TreeNode(7);

        System.out.println(zigzagLevelOrder(zigZagRoot));

        zigZagRoot = new TreeNode(1);
        zigZagRoot.left = new TreeNode(2);
        zigZagRoot.right = new TreeNode(3);
        zigZagRoot.left.left = new TreeNode(4);
        zigZagRoot.left.right = new TreeNode(5);

        System.out.println(zigzagLevelOrder(zigZagRoot));

        zigZagRoot = new TreeNode(1);
        zigZagRoot.left = new TreeNode(2);
        zigZagRoot.right = new TreeNode(3);
        zigZagRoot.left.left = new TreeNode(4);
        zigZagRoot.right.right = new TreeNode(5);

        System.out.println(zigzagLevelOrderNew(zigZagRoot));
    }

    public static List<List<Integer>> zigzagLevelOrderNew(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();

        // For Empty Tree
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;

        Boolean switchLevel = true;
        queue.offer(root);
        queue.offer(null);

        TreeNode temp;
        ArrayList<Integer> levelNodes = new ArrayList<>();
        while (!queue.isEmpty()) {
            temp = queue.poll();
            if (temp == null) {
                if (!queue.isEmpty()) {
                    result.add(levelNodes);
                    levelNodes = new ArrayList<>();
                    switchLevel = !switchLevel;
                    queue.add(null);
                } else {
                    result.add(levelNodes);
                }
                continue;
            }

            if (switchLevel) {
                levelNodes.add(temp.val);
            } else {
                levelNodes.add(0, temp.val);
            }

            if (temp.left != null) {
                queue.add(temp.left);
            }
            if (temp.right != null) {
                queue.add(temp.right);
            }
        }
        return result;
    }

    public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();

        // For Empty Tree
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;

        Boolean flag = true;
        queue.offer(root);

        TreeNode temp;

        while (!queue.isEmpty()) {
            ArrayList<Integer> levelNodes = new ArrayList<>();
            int len = queue.size();
            for (int i = 0; i < len; i++) {
                temp = queue.poll();
                if (flag) {
                    levelNodes.add(temp.val);
                } else {
                    levelNodes.add(0, temp.val);
                }
                if (temp.left != null)
                    queue.offer(temp.left);
                if (temp.right != null)
                    queue.offer(temp.right);
            }
            result.add(levelNodes);
            flag = !flag;
        }
        return result;
    }
}