一道算法题,有会的可以一起讨论下

const data = {

    name: 'A',
    child: [{
            name: 'AB',
            child: [{
                    name: 'AABA'
                },
                {
                    name: 'AABB'
                }
            ]
        },
        {
            name: 'AC',
            child: [{
                    name: 'AACA'
                },
                {
                    name: 'AACB'
                }
            ]
        }
    ]
}
// 请自行封装一个findPath的函数,实现如下效果
// 调用示例

findPath('AABB'); //["A", "AB", "AABB"]

findPath('AABA'); //["A", "AB", "AABA"]

findPath('AACB'); //["A", "AC", "AACB"]

findPath('AC'); //["A", "AC"]

findPath('AACA'); //["A", "AC", "AACA"]

阅读 684
评论
    4 个回答
    • 8.5k

    这种算法最适合用递归吧

    const findPath = (name, data, result = []) => {
      let _result;
      for (const item of data) {
        if (item.name === name) {
          return [...result, item.name];
        } else if (item.child) {
          _result = findPath(name, item.child, [...result, item.name]);
          if (_result) {
            return _result;
          }
        }
      }
    };
    
    findPath('AACB', [data]);

    @李十三 的观点很好,直接判断键名就能拿到结果了,只需一次计算,如果需要多次调用应该是最优解

    const dataReduce = (data, parent = [], result = {}) => {
      data.forEach(item => {
        result[item.name] = [...parent, item.name];
        item.child && dataReduce(item.child, result[item.name], result);
      });
      return result;
    };
    
    const _data = dataReduce([data]);
    
    _data['AACB'];//["A", "AC", "AACB"]
      • 11.5k
      const data = {
        'A': {name:'A',parent:undefined},
        'AB':{name:'AB',parent:'A'},
        'AABA':{name:'AABA',parent:'AB'},
        ...
      }

      我会先将数据转换成上面的结构缓存下来
      这样后面取的时候就简单多了

        • 2.5k
        const data = {
                name: 'A',
                child: [{
                    name: 'AB',
                    child: [{
                        name: 'AABA'
                    },
                        {
                            name: 'AABB'
                        }
                    ]
                },
                    {
                        name: 'AC',
                        child: [{
                            name: 'AACA'
                        },
                            {
                                name: 'AACB'
                            }
                        ]
                    }
                ]
            }
            function getAllKeys(data,result=[]){
                result.push(data.name);
                if(data.child){
                    for(let c of data.child){
                        getAllKeys(c,result);
                    }
                }
                return result;
            }
            const result=getAllKeys(data);
            function findPath(path){
                return result.filter(item=>path.indexOf(item)!=-1);
            }
            function wraplog(fun){
                return function addParams(...params){
                    const _r=fun(...params);
                    console.log(_r);
                    return _r;
                }
            }
            const _findPath=wraplog(findPath);
            _findPath('AABB'); //["A", "AB", "AABB"]
        
            _findPath('AABA'); //["A", "AB", "AABA"]
        
            _findPath('AACB'); //["A", "AC", "AACB"]
        
            _findPath('AC'); //["A", "AC"]
        
            _findPath('AACA'); //["A", "AC", "AACA"]
          • 655
          function findPath(obj, path) {
              var ret = [];
              var name = obj.name;
              var child = obj.child;
              check: if (name === path) {
                  ret.push(name);
                  break check;
              } else if (Array.isArray(child)) {
                  for (var i = 0; i < child.length; i++) {
                      var item = child[i];
                      var tmp = findPath(item, path);
                      if (tmp.length) {
                          ret = Array.prototype.concat.apply(ret, [name, tmp]);
                          break check;
                      }
                  }
              }
              return ret;
          }
          console.log(findPath(data, "AABB"));
            撰写回答

            登录后参与交流、获取后续更新提醒