[算法]一步步地将对象扁平化

小知识，大挑战！本文正在参与“程序员必备小知识”创作活动。

1、扁平化对象

最近看到一个算法题，写出一个flatten函数将下列对象扁平。

const obj = {
  a: 'a',
  b: [1,2,{c:[1,2,3,4]},4],
  c: { e: 5, f: 6 },
  d: undefined,
  f:[1,[1,2,[5,6]]]
};
//转换得到如下新数据结构:
const newobj = {
  a: 'a',
  'b[0]': 1,
  'b[1]': 2,
  'b[2].c[0]': 1,
  'b[2].c[1]': 2,
  'b[2].c[2]': 3,
  'b[2].c[3]': 4,
  'b[3]': 4,
  'c.e': 5,
  'c.f': 6,
  d: undefined,
  'f[0]': 1,
  'f[1][0]': 1,
  'f[1][1]': 2,
  'f[1][2][0]': 5,
  'f[1][2][1]': 6
}

首先我们看到这种数据结构去找他的转换规律，我们发现key:value如果是一般对象，通过 .一层一层的连接，如果是数组对象则通过[]一层一层连接，而且每次到根节点，则在newobj中新生成一条键值对，这是不是很像树的深度优先遍历？其实这个就是将对象遍历和深度优先遍历结合起来，拼接key值，直到根没有子节点返回的过程。

1、构造一个基本函数：

// 传入转换的对象
function flatten (obj){
  // 构造一个目标对象
  let newobj = {}

 // 返回目标对象
 return newobj
}

2、先不考虑key:value是数组情况，我们只考虑普通对象和基础数据类型。

// 传入转换的对象
function flatten (obj){
  // 构造一个目标对象
  let newobj = {}
  
  //定义一个判断是否是对象的简单函数
  function isobj (o){
   return typeof o==='object'&&o!=null
  }
  //开始遍历转换对象
  for(let key in obj){
  // 如果是对象
   if(isobj(obj[key])){
   // 进一步遍历，直到不是对象
   }else {
   //不是对象择直接添加进我们的新对象
   newobj[key] = obj[key]
   }
  
  }

 // 返回目标对象
 return newobj
}

3、额，写道这里好像有点问题，我们的遍历只有一层，下面如果还是对象就无法遍历了，这里应该使用深度优先遍历，我们重新构造一下。

// 传入转换的对象
function flatten (obj){
  // 构造一个目标对象
  let newobj = {}
  //定义一个判断是否是对象的简单函数
  function isobj (o){
   return typeof o==='object'&&o!=null
  }
  // 定义一个深度优先遍历函数
  let dsf = function(obj){
  //开始遍历转换对象
  for(let key in obj){
     // 如果是对象
    if(isobj(obj[key])){
      // 进一步遍历，直到不是对象
      dsf(obj[key])
    }else {
      //不是对象择直接添加进我们的新对象
      newobj[key] = obj[key]
    }
   }
  }
  //开始遍历
 dsf(obj)
 // 返回目标对象
 return newobj
}

4、我们已经遍历完了数据，接着就开始一层一层的拼接我们的新对象key值，在else处我们会结束掉key的拼接，开始新的拼接，注意：由于是一层一层拼接，每一层对象的key值我们都会保留他上一层拼接的key，所以这里我们需要将拼接的key传递下去。

// 传入转换的对象
function flatten (obj){
  // 构造一个目标对象
  let newobj = {}
  //定义一个判断是否是对象的简单函数
  function isobj (o){
   return typeof o==='object'&&o!=null
  }
  // 定义一个深度优先遍历函数
  let dsf = function(obj,newkey){
  //开始遍历转换对象
  for(let key in obj){
    //拼接当前key， newkey为空 就是第一次不拼接 .
    let cur = newkey?`${newkey}.${key}`:key
     // 如果是对象
    if(isobj(obj[key])){
      // 进一步遍历，直到不是对象
      dsf(obj[key],cur)
    }else {
      //不是对象择直接添加进我们的新对象
      newobj[cur] = obj[key]
    }
   }
  }
  //开始遍历
 dsf(obj,'')
 // 返回目标对象
 return newobj
}

5、接下来吧对数组的判断加上,修改一下cur。

// 传入转换的对象
function flatten (obj){
  // 构造一个目标对象
  let newobj = {}
  //定义一个判断是否是对象的简单函数
  function isobj (o){
   return typeof o==='object'&&o!=null
  }
  // 定义一个深度优先遍历函数
  let dsf = function(obj,newkey){
  //开始遍历转换对象
  for(let key in obj){
   //判断是不是数组
    let isarr = Array.isArray(obj)
    //拼接当前key， newkey为空 就是第一次不拼接 . []
    let cur = newkey?(isarr?`${newkey}[${key}]`:`${newkey}.${key}`):`${key}`
     // 如果是对象
    if(isobj(obj[key])){
      // 进一步遍历，直到不是对象
      dsf(obj[key],cur)
    }else {
      //不是对象择直接添加进我们的新对象
      newobj[cur] = obj[key]
    }
   }
  }
  //开始遍历
 dsf(obj,'')
 // 返回目标对象
 return newobj
}