一道递归数组面试题

题面

$a = [  
 '张三' => [  
    '李四' => [  
       '王五' => null,  
       '二六' => null  
     ],  
    '王峰' => [  
      '王芳' => null  
     ]  
 ],  
 '王麻子' => [  
     '小二' => null,  
     '小明' => [  
        '小灰' => null  
      ]  
 ]  
];  

要求写一个函数，输出这样的内容：

张三:李四 王峰 王五 二六  王芳
李四: 王五 二六
王峰:王芳
王麻子:小二 小明 小灰
小明:小灰

分析

• 直接递归，结果行首列 得张三，王麻子...与要求不符
• 分开递归，一部明确键即冒号左侧，另一部分处理右侧
• 故重构源，根据重建后的值域，收集键，即右侧实现

代码

// 1.重构源数据，确保键名有序
function rebuild($arr)
{
    $l = [];
    if (is_array($arr)) {
        $keys = array_keys($arr);
        for ($i=0;$i<count($keys);$i++) {
            if (is_null($arr[$keys[$i]])) {
                continue;
            }
            $l[$keys[$i]]=$arr[$keys[$i]];
            $l=array_merge($l, rebuild($l[$keys[$i]]));
        }
    }
    return $l;
}


// 2.递归收集值中的键
function recursive_keys($input)
{
    $output =  array_keys($input);
    foreach ($input as $v) {
        if (is_array($v)) {
            $output = array_merge($output, recursive_keys($v));
        }
    }
    return $output ;
}

// 3. 合并重组
function merge($arr)
{
    $rs = [];
    foreach(rebuild($arr) as $k => $v){
        $rs[$k] = recursive_keys($v);
        echo $k," : ",implode(" ", $rs[$k]),"\n";
    }
    return $rs;
}

merge($a);

效果

D:\code-base\algorithm\php>php "d:\code-base\algorithm\php\array\interview.php"
张三 : 李四 王峰 王五 二六 王芳
李四 : 王五 二六
王峰 : 王芳
王麻子 : 小二 小明 小灰
小明 : 小灰

本作品采用《CC 协议》，转载必须注明作者和本文链接