Categories
General

Binary tree – average sum Level – php – facebook


class Node {
  
  public $value;
  public $left;
  public $right;
  
  public function __construct(int $value) 
  {
    $this->value = $value;
   $this->left = null;
   $this->right = null;
  }
}



class Solution {

  public function bfs($node, &$hashmap, $level) 
  {
    
    if($node === null) {
      return;
    }

    
    $queue = new SplQueue();
  
    if($node->left)
    {
      $queue->enqueue($node->left);  
    }

    if($node->right)
    {
      $queue->enqueue($node->right);
    }


    
    while ($queue->count() > 0) {
    
      $childNode = $queue->pop();
      
      $hashmap[$level][] = $childNode->value;
      
        $this->bfs($childNode, $hashmap, $level + 1);
      
    }

    
  }
  
  public function AverageSumLevel($node) 
  {
    $hashmap = [];
    $level = 0;
    $hashmap[$level][] = $node->value;
    $this->bfs($node, $hashmap, $level + 1) ;
    
      
    foreach ($hashmap as $level => $values) 
    {
      $result[] = array_sum($values) / count($values);
    }
      
      
    return $result;
  }
}


$node5 = new Node(5);
$node5->left = new Node(4);
$node5->right = new Node(8);


$node5->left->left = new Node(2);
$node5->left->right = new Node(1);

$node5->right->right = new Node(9);
$node5->right->right->right = new Node(12);

$solution = new Solution();
$res = $solution->AverageSumLevel($node5);
var_dump($res);

Leave a Reply