$tree1 = [
    ['data' => 'A', 'left' => 1, 'right' => 2],
    ['data' => 'B', 'left' => 3, 'right' => 4],
    ['data' => 'C', 'left' => 5, 'right' => -1],
    ['data' => 'D', 'left' => -1, 'right' => -1],
    ['data' => 'E', 'left' => 6, 'right' => -1],
    ['data' => 'G', 'left' => 7, 'right' => -1],
    ['data' => 'F', 'left' => -1, 'right' => -1],
    ['data' => 'H', 'left' => -1, 'right' => -1],
];

$tree2 = [
    ['data' => 'G', 'left' => -1, 'right' => 4],
    ['data' => 'B', 'left' => 7, 'right' => 6],
    ['data' => 'F', 'left' => -1, 'right' => -1],
    ['data' => 'A', 'left' => 5, 'right' => 1],
    ['data' => 'H', 'left' => -1, 'right' => -1],
    ['data' => 'C', 'left' => 0, 'right' => -1],
    ['data' => 'D', 'left' => -1, 'right' => -1],
    ['data' => 'E', 'left' => 2, 'right' => -1],
];

function findroot($tree)
{
    $list = array_pad([], count($tree), false);
    foreach ($tree as $item) {
        if ($item['left'] != -1) {
            $list[$item['left']] = true;
        }
        if ($item['right'] != -1) {
            $list[$item['right']] = true;
        }
    }
    return array_search(false, $list);
}

function ismorphic($r1, $r2)
{
    global $tree1;
    global $tree2;

    if (($r1 == -1) && ($r2 == -1)) {
        return true;
    }
    if ((($r1 == -1) && ($r2 != -1)) || (($r1 != -1) && ($r2 == -1))) {
        return false;
    }
    if ($tree1[$r1]['data'] != $tree2[$r2]['data']) {
        return false;
    }
    if (($tree1[$r1]['left'] == -1) && ($tree2[$r2]['left'] == -1)) {
        return ismorphic($tree1[$r1]['right'], $tree2[$r2]['right']);
    }
    if (($tree1[$r1]['left'] != -1) && ($tree2[$r2]['left'] != -1)) {
        return ismorphic($tree1[$r1]['left'], $tree2[$r2]['left']) && ismorphic($tree1[$r1]['right'], $tree2[$r2]['right']);
    } else {
        return ismorphic($tree1[$r1]['left'], $tree2[$r2]['right']) && ismorphic($tree1[$r1]['right'], $tree2[$r2]['left']);
    }
}

$r1 = findroot($tree1);
$r2 = findroot($tree2);
$res = ismorphic($r1, $r2);

最后更新于 2021-07-12 09:41:28 并被添加「」标签，已有 635 位童鞋阅读过。