A good problem to practice (BFS + DFS)


  • 17

    BFS:

        public List<Double> averageOfLevels(TreeNode root) {
            List<Double> list = new LinkedList<>();
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                int count = queue.size();
                double sum = 0;
                for (int i = 0; i < count; i++) {
                    TreeNode cur = queue.poll();
                    sum += cur.val;
                    if (cur.left != null) queue.offer(cur.left);
                    if (cur.right != null) queue.offer(cur.right);
                }
                list.add(sum / count);
            }
            return list;
        }
    

    DFS: a new node class make it more readable and professional

        class Node {
            double sum;
            int count;
            Node (double d, int c) {
                sum = d;
                count = c;
            }
        }
        public List<Double> averageOfLevels(TreeNode root) {
            List<Node> temp = new ArrayList<>();
            helper(root, temp, 0);
            List<Double> result = new LinkedList<>();
            for (int i = 0; i < temp.size(); i++) {
                result.add(temp.get(i).sum / temp.get(i).count);
            }
            return result;
        }
        public void helper(TreeNode root, List<Node> temp, int level) {
            if (root == null) return;
            if (level == temp.size()) {
                Node node = new Node((double)root.val, 1);
                temp.add(node);
            } else {
                temp.get(level).sum += root.val;
                temp.get(level).count++;
            }
            helper(root.left, temp, level + 1);
            helper(root.right, temp, level + 1);
        }
    

Log in to reply
 

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