树

• 介绍下深度优先遍历（DFS）和广度优先遍历（BFS），如何实现？
• 请分别用深度优先思想和广度优先思想实现一个拷贝函数？
• 实现 convert 方法
• 找出链条中所有的父级id

介绍下深度优先遍历（DFS）和广度优先遍历（BFS），如何实现？

查看答案

• 深度优先遍历（DFS）—— 是指从某个顶点出发，首先访问这个顶点，然后找出刚访问 这个结点的第一个未被访问的邻结点，然后再以此邻结点为顶点，继续找它的 下一个顶点进行访问。重复此步骤，直至所有结点都被访问完为止。
• 广度优先遍历（BFS）—— 是从某个顶点出发，首先访问这个顶点，然后找出刚访问这 个结点所有未被访问的邻结点，访问完后再访问这些结点中第一个邻结点的所 有结点，重复此方法，直到所有结点都被访问完为止。

function deepTraversal(node) {
    let nodes = []
    if (node != null) {
        nodes.push[node]
        let childrens = node.children
        for (let i = 0; i < childrens.length; i++) deepTraversal(childrens[i]) 
    }
    return nodes
} 

function deepTraversal(node) {
    let nodes = []
    if (node != null) {
        // 同来存放将来要访问的节点
        let stack = []
        stack.push(node)
        while (stack.length != 0) {
            //正在访问的节点
            let item = stack.pop()
            nodes.push(item)
            let childrens = item.children
            for ( let i = childrens.length - 1; i >= 0; i--)
            // 将现在访问点的节点的子节点存入 stack，供将来访问 )
            stack.push(childrens[i])
        }
    }
    return nodes
} 

function wideTraversal(node) {
    let nodes = [], i = 0
    if (node != null) {
        nodes.push(node)
        wideTraversal(node.nextElementSibling)
        node = nodes[i++]
        wideTraversal(node.firstElementChild)
    }
    return nodes
}

function wideTraversal(node) {
    let nodes = [], i = 0
    while (node != null) {
        nodes.push(node)
        node = nodes[i++]
        let childrens = node.children
        for (let i = 0; i < childrens.length; i++) {
            nodes.push(childrens[i])
        } 
    }
    return nodes
}

请分别用深度优先思想和广度优先思想实现一个拷贝函数？

查看答案

let _toString = Object.prototype.toString
let map = {
    array: 'Array',
    object: 'Object',
    function: 'Function',
    string: 'String',
    null: 'Null',
    undefined: 'Undefined',
    boolean: 'Boolean',
    number: 'Number'
}
let getType = (item) => {
    return _toString.call(item).slice(8, -1)
}
let isTypeOf = (item, type) => {
    return map[type]
}

实现 convert 方法

把原始 list 转换成树形结构， 要求尽可能降低时间复杂度。
以下数据结构中，id代表部门编号，name是部门名称，parentId是父部门编号，为0代表一级部门。
现在要求实现一个 convert 方法，把原始 list 转换成树形结构
parentId 为多少就挂载在该 id 的属性 children 数组下，结构如下：

查看具体实例

let list = [
    {id: 1,name: '部门 A',parentId: 0}, 
    {id: 2,name: '部门 B',parentId: 0}, 
    {id: 3,name: '部门 C',parentId: 1}, 
    {id: 4,name: '部门 D',parentId: 1}, 
    {id: 5,name: '部门 E',parentId: 2}, 
    {id: 6,name: '部门 F',parentId: 3}, 
    {id: 7,name: '部门 G',parentId: 2}, 
    {id: 8,name: '部门 H',parentId: 4}];
const result = convert(list, ...);

转换后

let result = [{
    id: 1,
    name: '部门 A',
    parentId: 0,
    children: [{
            id: 3,
            name: '部门 C',
            parentId: 1,
            children: [{
                id: 6,
                name: '部门 F',
                parentId: 3
            }, {
                id: 16,
                name: '部门 L',
                parentId: 3
            }]
        }, {
            id: 4,
            name: '部门 D',
            parentId: 1,
            children: [{
                id: 8,
                name: '部门 H',
                parentId: 4
            }]
        }
    ]
}, ···]

查看答案

• 这里使用了对象的引用，将list改成键值对形式
• 修改键值对的时候，结果数组中的值也跟着变化
• 箭头函数+逗号运算符，最后一个是返回值

function convert(list) {
    const res = []
    const map = list.reduce((res, v) => (res[v.id] = v, res), {})
    /*
        {1: {id: 1,name: '部门 A',parentId: 0}}
        {2: {id: 2,name: '部门 B',parentId: 0}}
        ...
    */
    for (const item of list) {
        // 如果是根数据就直接放进结果数组
        if (item.parentId === 0) {
            res.push(item)
            continue
        }
        // 判断父节点是否在map中
        if (item.parentId in map) {
            const parent = map[item.parentId]
            parent.children = parent.children || []
            // 直接在map中修改，数组中的对象也跟着修改
            parent.children.push(item)
        }
    }
    return res
}

找出链条中所有的父级id

例如：

1. 如果输入 '11',那么返回 ['1','11']
2. 如果输入 '112',那么返回 ['1','11','112]
3. 如果输入 '122',那么返回 ['1','12','122]
4. 如果输入 '113',那么返回 []
5. 如果输入 '1114',那么返回 []

const data = [{
    id: "1",
    name: "test1",
    children: [{
        id: "11",
        name: "test11",
        children: [{
            id: "111",
            name: "test111"
        }, {
            id: "112",
            name: "test112"
        }]
    }, {
        id: "12",
        name: "test12",
        children: [{
            id: "121",
            name: "test121"
        }, {
            id: "122",
            name: "test122"
        }]
    }]
}];

查看答案

const find = str => {
    let result = [];
    let findArr = data;
    let skey = "";
    // 遍历字符串
    for (let i = 0, l = str.length; i < l; i++) {
        skey += str[i];
        let item = findArr.find(item => {
            return item.id == skey;
        });
        if (!item) {
            return [];
        }
        result.push(item.id);
        // 如果字符串已经完成遍历直接返回
        if (i == l - 1) return result;
        // 没有就判断是否有孩子节点
        if (item.children) {
            findArr = item.children;
        }
    }
};