一个对象，其实就是一棵树，对于一棵树而言，很多时候，我们可能想知道它到底有多深，因此，这里需要实现一个算法
getDeeps，去获取一个对象的深度
分析
对于一个对象而言，其实就是大对象套用小对象，其实基本思路应该很简单，就是利用递归，计算出每一个子节点的深度，然后再加上1就OK了。比如对于数字、字符串、数组等，可能就没有深度，那么他们的深度可以理解为1，而对于实际的对象，那么可以再通过递推去计算。
存在问题
这么一看似乎没问题了，但是，如果处理不好，那就会存在一个致命的问题，那就是循环引用，如果一个子节点可能还会引用自己，那么如果通过简单的遍历就会进入死循环。所以需要去考虑循环引用。
代码实现
/**
* 获取一个对象的深度
* parents 为 true 说明需要考虑循环引用 否则不需要
* @param {*} obj
*/
function getDeeps(obj,parents) {
if(parents == true) {
parents = [];
}
if (obj && obj instanceof Object && !(obj instanceof Array) && (!parents || parents.indexOf(obj) < 0)) {
let max = null;
let flag = false;
for (let key in obj) {
let dep = getDeeps(obj[key],!parents ? parents : parents.concat(obj)) + 1;
if (!flag) {
flag = true;
max = dep
} else {
max = max < dep ? dep : max;
}
}
return max;
} else {
return 0;
}
};
module.exports = getDeps;
这里引入了parents选项。当parents为true时表示需要考虑循环引用，否则代表不需要考虑循环引用。
这里面parents其实就是一个数组，记录了某个深度节点之前的所有的父节点。如此一来，便可以通过遍历parents来获知是否有循环引用。
是否要改进Array
问题似乎解决了，但是又似乎总有点不尽人意，因为每个节点都有一个与众不同的parents去维护自己的父节点。而parents是一个数组，indexOf相当于每次都需要经历一个平均是n/2的时间复杂度的遍历。那么是不是可以有办法改进呢?
似乎可以使用es6的map或者set，对于set而言，在插入时可能存在一定的性能问题，但是获取元素时会很快，具体可以参考这篇文章
这篇文章对set、Array的插入、获取性能做了对比，基本结果如下:
Array
Set
三行分别表示的是:
- 插入
10000 * 1000条数据消耗的时间。 - 新插入一条数据消耗的时间
- 获取某条数据消耗的时间
可以看到，Set的插入性能比Array低很多，但是读取性能却比Array快很多，几乎是瞬间的。
那么，对于Map呢，于是，做了一个同样的比较:
let s = new Map();
let begin = new Date().getTime();
for(let i = 0; i < 10000 * 1000;i++) {
s.set(i,true);
};
let end = new Date().getTime();
console.log(`消耗${end-begin}ms`);
begin = new Date().getTime();
s.set(10000 * 10000 - 1,true);
end = new Date().getTime();
console.log(`添加消耗${end-begin}ms`);
begin = new Date().getTime();
s.get(10000 * 10000 - 1);
end = new Date().getTime();
console.log(`判断消耗${end-begin}ms`);
结果如下:
可以看到，消耗的时间远远的多于
Array和Set。
综合以上，其实使用Array或者Set是最合适的，对于需要大量查找的是Set更合适，但是，查找深度的时候，每一个子节点都需要相当于新建一个分支，生成一个新的Set,从Set的插入性能来看，是不合适的。因此，用Array是最合适的，不需要改进。
