Unival - PHP Online
Form of PHP Sandbox
Enter Your PHP code here for testing/debugging in the Online PHP Sandbox. As in the usual PHP files, you can also add HTML, but do not forget to add the tag <?php
in the places where the PHP script should be executed.
Result of php executing
Full code of Unival.php
- <?php
- class Node {
- private $children;
- private $value;
- public function value() {
- return $this->value;
- }
- public function __construct($value) {
- $this->value = $value;
- $this->children = [];
- }
- /**
- * @returns Node[]
- */
- public function children() {
- return $this->children;
- }
- /**
- * @param Node $child
- * @returns void
- */
- public function addChild($child) {
- $this->children[] = $child;
- }
- }
- class UnivalUtils {
- /**
- * @param Node $node
- * @returns bool
- */
- public static function isUnival($node) {
- // Empty tree is considered unival
- if ($node === null) {
- return true;
- }
- // Leaf node: wind the recursion upwards from here starting at true
- if (empty($node->children())) {
- return true;
- }
- $isUnival = true;
- foreach ($node->children() as $child) {
- $isUnival =
- $isUnival
- && ($node->value() === $child->value())
- && self::isUnival($child);
- }
- return $isUnival;
- }
- /**
- * @param Node $node
- * @returns int
- */
- public static function countUnivalSubtrees($node) {
- // Base case: null $node, return 1 b/c null tree is considered Unival
- if ($node === null) {
- return 1;
- }
- // Base case: leaf node, return 1 b/c each leaf is its own Unival tree
- if (empty($node->children())) {
- return 1;
- }
- $univalSubtreesCount = 0;
- foreach ($node->children() as $child) {
- if (self::isUnival($child)) {
- $univalSubtreesCount += self::countUnivalSubtrees($child);
- }
- }
- if (self::isUnival($node)) {
- $univalSubtreesCount++;
- }
- return $univalSubtreesCount;
- }
- }
- /**
- * 3
- * 3 3 3
- * 3 3 3 3 3 3
- */
- $root = new Node(3);
- $rootChild1 = new Node(3);
- $rootChild1Child1 = new Node(3);
- $rootChild1Child2 = new Node(3);
- $rootChild1->addChild($rootChild1Child1);
- $rootChild1->addChild($rootChild1Child2);
- $root->addChild($rootChild1);
- $rootChild2 = new Node(3);
- $rootChild2Child1 = new Node(3);
- $rootChild2Child2 = new Node(3);
- $rootChild2->addChild($rootChild2Child1);
- $rootChild2->addChild($rootChild2Child2);
- $root->addChild($rootChild2);
- $rootChild3 = new Node(3);
- $rootChild3Child1 = new Node(3);
- $rootChild3Child2 = new Node(3);
- $rootChild3->addChild($rootChild3Child1);
- $rootChild3->addChild($rootChild3Child2);
- $root->addChild($rootChild3);
- print_r('Number of Unival subtrees found in Tree: ' . UnivalUtils::countUnivalSubtrees($root));
File Description
- Unival
- PHP Code
- 29 Jan-2020
- 2.76 Kb
You can Share it:
Latest PHP Pastes