前端笔试中两道与节点有关的算法题

荆兆峰发布于2019-08-26 13:37 / 3208人阅读

摘要：分别用广度优先遍历和深度优先遍历展开下面节点示例广度优先遍历输出结果深度优先遍历输出结果关系型数组转换成树形结构对象类似期望输出代码

1.分别用广度优先遍历和深度优先遍历展开下面节点

示例

var tree = {
    name: "root",
    children: [{
        name: "child1",
        children: [{
            name: "child1_1",
            children: []
        }, { name: "child1_2", children: [] }]
    }, {
        name: "child2",
        children: [{
            name: "child2_1",
            children: []
        }]
    }, {
        name: "child3",
        children: [{
            name: "child2_1",
            children: []
        }]
    }]
};

广度优先遍历：

function wideTraversal(node) {
    var nodes = [];
    if (node != null) {
        var queue = [];
        queue.unshift(node);
        while (queue.length != 0) {
            var item = queue.shift();
            nodes.push(item.name);
            var children = item.children;
            for (var i = 0; i < children.length; i++) {

                queue.push(children[i]);
            }
        }

    }
    return nodes;
}
console.log(wideTraversal(tree))

输出结果：

[ "root","child1","child2","child3","child1_1","child1_2","child2_1","child2_1" ]

深度优先遍历：

function traverseTree(node) {
    var child = node.children,
        arr = [];

    arr.push(node.name);
    if (child) {
        child.forEach(function(node) {
            arr = arr.concat(traverseTree(node));
        });
    }
    return arr;
}
console.log(traverseTree(tree))

输出结果：

[ "root","child1","child1_1","child1_2","child2","child2_1","child3","child2_1" ]

2.关系型数组转换成树形结构对象

类似：

var data = [
    { parentId: 0, id: 1, value: "1" },
    { parentId: 3, id: 2, value: "2" },
    { parentId: 0, id: 3, value: "3" },
    { parentId: 1, id: 4, value: "4" },
    { parentId: 1, id: 5, value: "5" }
]

期望输出：

[
{id:1,value:"1",
children:[{id:4,value:"4",children:[]},
{id:5,value:"5",children:[]}]},
{id:3,value:"3",
children:[id:2,value:"2",children:[]]}]

代码：

var getJsonTree = function(data, parentId) {
    var itemArr = [];
    for (var i = 0; i < data.length; i++) {
        var node = data[i];
        //data.splice(i, 1)
        if (node.parentId == parentId) {
            var newNode = { id: node.id, value: node.value, children: getJsonTree(data, node.id) };
            itemArr.push(newNode);
        }
    }
    return itemArr;
}
console.log(getJsonTree(data, 0))

GPU云服务器云服务器笔试面试题 java笔试sql题最难的算法题 web前端笔试

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/109185.html

分享两道大厂前端面试题

摘要：示例输入输出示例输入输出第一种方法滑动窗口解法滑动窗口两个边界情况第二种方法位运算解法位运算头条财经部门一面二维数组的回形遍历这是头条财经部门一面的一道题记住遍历过的索引更多前端算法题，参见算法仓库。 1. 百度百家号一面面完回来搜素，才发现这道题其实是LeetCode540。 540 medium 有序数组中的单一元素给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数...

whjin 2019-08-26 14:04 评论0 收藏0
leetcode上两道题的思考

摘要：求出满足这样要求的路径的数目，并返回。第二道题给定一个数，将其拆分为个平方数的和，求最小的。这道题不能用贪心算法求解。当时，如果用贪心算法，结果就是，返回。假设给出的数字为。第三轮减，得到，将放入队列中。第一道题：给定一棵二叉树，在二叉树的所有路径中找到路径上结点之和为题目给定值的子路径。路径不一定以根节点为开头，也不一定以叶节点为结尾。并且根据分析路径之间应该可以重叠。求出满足这样...

zhangxiangliang 2019-07-31 11:05 评论0 收藏0
一次前端笔试总结

摘要：另外，原题还有字数限制的，只有在字数小于并且结果正确时才可以满分。插入节点操作的可以使用和方法，随便用一个都行。但是，这题有两个限制条件优雅的方式前个元素。 1.有一个长度未知的数组a，如果它的长度为0就把数字1添加到数组里面，否则按照先进先出的队列规则让第一个元素出队。分析：这道题主要是考核了数组的队列方法和栈方法。另外，原题还有字数限制的，只有在字数小于30并且结果正确时才可以满...

jsdt 2019-08-30 13:50 评论0 收藏0
一次前端笔试总结

摘要：另外，原题还有字数限制的，只有在字数小于并且结果正确时才可以满分。插入节点操作的可以使用和方法，随便用一个都行。但是，这题有两个限制条件优雅的方式前个元素。 1.有一个长度未知的数组a，如果它的长度为0就把数字1添加到数组里面，否则按照先进先出的队列规则让第一个元素出队。分析：这道题主要是考核了数组的队列方法和栈方法。另外，原题还有字数限制的，只有在字数小于30并且结果正确时才可以满...

GitChat 2019-08-21 17:17 评论0 收藏0