Java iterative BFS


  • 0
    J
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            List<List<Integer>> result = new ArrayList<>();
            if (root == null) return result;
            Stack<TreeNode> level = new Stack<>();
            level.push(root);
            boolean leftFirst = true;
            while (!level.isEmpty()) {
                Stack<Integer> values = new Stack<>();
                Stack<TreeNode> nextLevel = new Stack<>();
                while (!level.isEmpty()) {
                    TreeNode node = level.pop();
                    values.push(node.val);
                    if (leftFirst) {
                        if (node.left != null) nextLevel.push(node.left);
                        if (node.right != null) nextLevel.push(node.right);
                    } else {
                        if (node.right != null) nextLevel.push(node.right);
                        if (node.left != null) nextLevel.push(node.left);
                    }
                    
                }
                result.add(values);
                level = nextLevel;
                leftFirst = !leftFirst;
            }
            return result;
        }
    

Log in to reply
 

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