build-and-print-tree笔试题

搞到一份面试题,看了半天无解,最后万能的陈哥给出了答案。陈哥太强了yyds!!!

原题如下:

<?php 

// 需求描述

// 对于给定的如下数据结构,请完善 TreeBuilder 和 TreePrinter 的实现,然后在控制台中输出整个 Tree 的结构。


// 给定的数据,id 为主键,parent 为父节点的 id,parent 为 0 是为根节点。
$data = [
    [
        'id' => 1,
        'parent' => 0,
    ],
    [
        'id' => 2,
        'parent' => 1,
    ],
    [
        'id' => 3,
        'parent' => 1,
    ],
    [
        'id' => 4,
        'parent' => 3,
    ],
    [
        'id' => 5,
        'parent' => 3,
    ],
    [
        'id' => 6,
        'parent' => 0,
    ],
    [
        'id' => 7,
        'parent' => 6,
    ],
];


// 节点的数据结构
class Node {
    public $id;
    public $children;
    public function __construct($id, $children) 
    {
        $this->id = $id;
        $this->children = $children;
    }
}

// 根据原始的数据,构建 Tree 结构, 需要实现 build() 方法
class TreeBuilder {

    protected $data = [];

    public function __construct(array $data) 
    {
        $this->data = $data;
    }

    public function  build(): Node
    {
        return new Node(0, []);
    }
}

// 打印 Tree 的内部结构, 实现 print() 方法
class NodePrinter {
    protected $node;

    public function __construct(Node $node) {
        $this->node = $node;
    }

    public function print() 
    {
        // your code
    }
}


/*
最后调用 TreeBuilder 和 NodePrinter,这三行代码应该输出如下结果:

0
--1
----2
----3
------4
------5
--6
----7
*/


$builder = new TreeBuilder($data);
$printer = new NodePrinter($builder->build());
$printer->print();

答案

public function print()
{
    global $data;
    echo '<pre>';
    $refer = [];
    $tree = [];
    $list = [];
    foreach ($data as $key => $value) {
        $refer[$value['id']] = &$data[$key];
    }
    foreach ($data as $k => $v) {
        if ($v['parent'] == $this->node->id) {
            $data[$key]['string'] = 1;
            $tree[] = &$data[$k];
        } else {
            if (isset($refer[$v['parent']])) {
                $pack = &$refer[$v['parent']];
                $data[$k]['string'] = $pack['string'] + 1;
                $pack['children'][] = &$data[$k];
            }
        }
        $list[] = $data[$k];
    }
    echo '0' . PHP_EOL;
    foreach ($list as $v) {
        echo str_repeat('--', $v['string'] + 1) . $v['id'] . PHP_EOL;
    }
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注