Advertisement
korobushk

average bfs ,by level average binary tree

May 16th, 2021
784
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.30 KB | None | 0 0
  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     public List<Double> averageOfLevels(TreeNode root) {
  18.               Queue<TreeNode>queue = new LinkedList<>();
  19.               List<Double> list = new ArrayList<>();
  20.             int count = 0;
  21.             double sum = 0;
  22.       if (root == null) {
  23.             return null;
  24.           }
  25.        
  26.       queue.add(root);
  27.       while(!queue.isEmpty()){
  28.           int numberOfNodes = queue.size();
  29.              
  30.           while(numberOfNodes>0){
  31.           TreeNode presentNode = queue.remove();
  32.                 sum+=presentNode.val;
  33.                 count++;
  34.           if(presentNode.left!=null){
  35.               queue.add(presentNode.left);
  36.           }
  37.            if(presentNode.right!=null){
  38.               queue.add(presentNode.right);
  39.           }
  40.      
  41.                 numberOfNodes--;
  42.           }      
  43.           list.add(sum/count);
  44.           sum = 0;
  45.           count = 0;
  46.       }
  47.       return list;
  48.     }
  49. }
  50.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement