PHP面试问题，有大佬知道这个怎么写吗

Question

Answer 1

1、找到第一层，然后根据第一层进行递归查找即可
2、这道算法题对于初学者而言的确有点绕，希望好好研究一下我写逻辑哈

• PHP代码如下：

<?php
$tree = [
    ['node' => 2, 'children' => [3, 9, 4]],
    ['node' => 7, 'children' => [2]],
    ['node' => 3, 'children' => [6]],
    ['node' => 4, 'children' => [5]],
    ['node' => 5, 'children' => [8]],
    ['node' => 10, 'children' => [11]]
];

// 先将子元素合并
$children = [];
foreach ($tree as $k => $v) {
    $children = array_merge($children, $v['children']);
}

// 找出第一层
$loop = [];
foreach ($tree as $item) {
    if (!in_array($item['node'], $children)) {
        $loop[] = $item['node'];
    }
}

// 递归找结果
function recursion(&$tree, $loop)
{
    // 一定要加staic，不然每次进来就清空了
    static $result = [];
    $result = array_merge($result, $loop);

    if ($tree) {
        $next_children = [];
        foreach ($tree as $k => $item) {
            if (in_array($item['node'], $loop)) {
                // 下一次要循环的元素
                $next_children = array_merge($next_children, $item['children']);
                // 找完就删除
                unset($tree[$k]);
            }
        }
        // 递归查找
        return recursion($tree, $next_children);
    } else {
        // 返回最终结果
        return $result;
    }
}

$result = recursion($tree, $loop);

print_r($result);

// 结果
// Array ( [0] => 7 [1] => 10 [2] => 2 [3] => 11 [4] => 3 [5] => 9 [6] => 4 [7] => 6 [8] => 5 [9] => 8 )

已参与了 SegmentFault 思否社区 10 周年「问答」打卡 ，欢迎正在阅读的你也加入。

Answer 2

写一下伪代码。

1. 遍历一下整个数组，设定children->parent关系，例如2->7,3->2,9->2,4->2,以此类推。
2. 没有children->parent关系的节点，为根节点，如7,10
3. 以7,10节点为开始，做广度优先遍历。第一层7,10。第二层遍历7,10的children 2,11。第三层遍历2,11的children 3,9,4，以此类推。

已参与了 SegmentFault 思否社区 10 周年「问答」打卡 ，欢迎正在阅读的你也加入。

Answer 3

做树形整理，把树高弄出来，然后按树高+根节点+父节点的方式排序输出就行了。

这种应该是把逻辑写清楚，代码意思差不多就行了，好几十行写的也累看的也累，运行基本不可能一次过。

已参与了 SegmentFault 思否社区 10 周年「问答」打卡 ，欢迎正在阅读的你也加入。

Answer 4

不会写php,写了个python参考一下吧, 就是基础的广度优先搜索(bfs).

from typing import *
from collections import Counter
import queue

tree = {
    2: [3, 9, 4],
    7: [2],
    3: [6],
    4: [5],
    5: [8],
    10: [11]
}

degree = Counter()
for k in tree.keys():
    degree[k] = 0
for vs in tree.values():
    for v in vs:
        degree[v] += 1

q = queue.Queue()
ans = []
for k, v in degree.items():
    if v == 0:
        q.put(k)

while not q.empty():
    node = q.get()
    ans.append(node)
    if node in tree:
        for nxt in tree[node]:
            q.put(nxt)

print(ans)