建立二元樹

建立二元樹

<?php

class TreeNode {
    public function __construct(
        public $value = 0,
        public ?TreeNode $left = null,
        public ?TreeNode $right = null,
    ) {
    }
}

function buildTree(array $targets,int $start, int $end): ?TreeNode {
    if ($start > $end) {
        return null;
    }
    $middle = floor(($start + $end) / 2);
    $tree = new TreeNode($targets[$middle]);
    $tree->left= buildTree($targets, $start, $middle - 1);
    $tree->right = buildTree($targets, $middle + 1, $end);
    
    return $tree;
}
// 種樹
$list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
$root = buildTree($list, 0, count($list) - 1);
// 驗證結果
$stack = [];
$current = $root; // 複製指標
while($current || !empty($stack)) {
    while($current) {
        $stack[] = $current;
        $current = $current->left;
    }
    $current = array_pop($stack);
    echo $current->value;
    $current = $current->right;
}