Java O(n) solution using LinkedList<LinkedList<Integer>> (no reversing)


  • 1
    S

    Java LinkedList is doubly, so adding to head and tail is O(1), and this code does not do any searches in the linked lists. I'm fairly sure it's O(n), but feel free to let me now if I'm wrong.

    public class Solution {
        public List<List<Integer>> levelOrderBottom(TreeNode root) {
            LinkedList<List<Integer>> lob = new LinkedList<List<Integer>>();
            if (root == null) return lob;
            LinkedList<Integer> row = new LinkedList<Integer>();
            TreeNode depth = null;
            Queue<TreeNode> q = new LinkedList<TreeNode>();
            q.add(root);
            while (!q.isEmpty()) {
                TreeNode n = q.remove();
                if (n == depth) {
                    lob.addFirst(row);
                    row = new LinkedList<Integer>();
                    depth = null;
                }
                row.add(n.val);
                if (n.left != null) {
                    if (depth == null) {
                        depth = n.left;
                    }
                    q.add(n.left);
                }
                if (n.right != null) {
                    if (depth == null) {
                        depth = n.right;
                    }
                    q.add(n.right);
                }
            }
            lob.addFirst(row);
            return lob;
        }
    }

Log in to reply
 

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