阿里面试题树的深度优先遍历

向右看齐 2022-05-15 01:18 233阅读 0赞

前几天内推阿里的前端，自己本来就是菜鸟，面试官让做一道编程题，20分钟。我看到编程题，树的深度优先遍历，这名字让我想到了图的深度优先遍历，心想完了，完了，图的算法我根本不熟悉啊，于是心态就崩了，最后面试也失败了。

后来自己静下心来看这道题，发现并不难，题目如下：

//请使用 JavaScript 编写一个树的深度优先遍历函数（节点最深的最先访问到，依次类推），满足以下测试用例：
    
    // 假设树的结构如下
    
    const tree = [
      {
        id: 1,
        name: '张三',
        children: [
            {
                id: 2,
                name: '李四',
                children: [
                    {
                        id: 5,
                        name: '张五'
                    }
                ]
            }
        ]
      },
      {
        id: 6,
        name: '玛丽'
      }
    ]
    
    
    // 测试用例：
    
    // 1. 生成一颗新树，将所有节点的id，加1
    console.log(treeMap(tree, node => {
        let newNode = { ...node }
        newNode.id = node.id + 1
        return newNode
    }))
    
    // 打印的新树，应该与tree的结构一致，只是每个id自增1，老的tree，应该没有任何改动
    
    // 2. 打印每个节点的id
    treeMap(tree, node => {
        console.log(node.id)
        return node
    });
    
    
    // 应打印顺序应该是： 5，2，1，6
    
    
    // 3. 对于非法输入，应直接返回第一个入参
    console.log(treeMap(null)) // 输出null
    console.log(treeMap(tree, true/*不是函数*/)) //输出tree

我的解答如下

function treeMap(tree, f){ 
        const newtree = [];
        if (!(f instanceof Function)){
            return tree;
        }
        if (tree instanceof Array){
            for (let item of tree){
                const obj = Object.assign({}, item) //这里要注意克隆一下节点，不然会影响老树的结构
                if (item.hasOwnProperty("children")){
                    obj.children = treeMap(item.children,f)
                }
                newtree.push(f(obj))
            }
        }
        return newtree
    }