Java iterative and recursive solutions.


  • 4
    C
    // bfs 
    public List<List<Integer>> zigzagLevelOrder1(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int l = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node != null) {
                    level.add(node.val);
                    queue.add(node.left);
                    queue.add(node.right);
                }
            }
            if (!level.isEmpty()) {
                if (l % 2 == 1) {
                    Collections.reverse(level);
                }
                ret.add(level);
            }
            l++;
        }
        return ret;
     }
     
     // dfs recursively
     public List<List<Integer>> zigzagLevelOrder2(TreeNode root) {
         List<List<Integer>> ret = new ArrayList<>();
         dfs(root, 0, ret);
         return ret;
     }
     
     private void dfs(TreeNode node, int l, List<List<Integer>> ret) {
         if (node != null) {
             if (l == ret.size()) {
                 List<Integer> level = new ArrayList<>();
                 ret.add(level);
             }
             if (l % 2 == 1) {
                ret.get(l).add(0, node.val);  // insert at the beginning
             } else {
                ret.get(l).add(node.val);
             }
             dfs(node.left, l+1, ret);
             dfs(node.right, l+1, ret);
         }
     }
     
     // dfs iteratively
     // import javafx.util.Pair;
     public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
         List<List<Integer>> ret = new ArrayList<>();
         Deque<Pair<TreeNode, Integer>> stack = new LinkedList<>();
         stack.push(new Pair(root, 0));
         while (!stack.isEmpty()) {
             Pair<TreeNode, Integer> p = stack.pop();
             TreeNode node = p.getKey();
             int l = p.getValue();
             if (node != null) {
                if (l == ret.size()) {
                    ret.add(new ArrayList<>());
                }
                if (l % 2 == 1) {
                    ret.get(l).add(0, node.val);
                } else {
                    ret.get(l).add(node.val);
                }
                stack.push(new Pair(node.right, l+1));
                stack.push(new Pair(node.left, l+1));
             }
         }
         return ret;
     }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.