Java BFS iterative and DFS recursive solution


  • 0

    bfs

      public class Solution {
            public List<List<Integer>> levelOrder(TreeNode root) {
                List<List<Integer>> list = new ArrayList<>();
                Queue<TreeNode> queue = new LinkedList<>();
                if (root != null) {
                    queue.offer(root);
                }
                while (!queue.isEmpty()) {
                    int size = queue.size();
                    List<Integer> level = new ArrayList<>();
                    for (int i = 0; i < size; i++) {
                        root = queue.poll();
                        level.add(root.val);
                        if (root.left != null) {
                            queue.offer(root.left);
                        }
                        if (root.right != null) {
                            queue.offer(root.right);
                        }
                    }
                    list.add(level);
                }
                return list;
            }
        }
    

    dfs: for nodes in each level are added in the order from leftmost to rightmost.

    public class Solution {
        public List<List<Integer>> levelOrder(TreeNode root) {
            List<List<Integer>> list = new ArrayList<>();
            levelOrderHelper(list, 0, root);
            return list;
        }
        
        private void levelOrderHelper(List<List<Integer>> list, int level, TreeNode root) {
            if (root == null) {
                return;
            }
            if (level == list.size()) {
                list.add(new ArrayList<>());
            }
            list.get(level).add(root.val);
            levelOrderHelper(list, level + 1, root.left);
            levelOrderHelper(list, level + 1, root.right);
        }
    }

Log in to reply
 

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