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

Question

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"]

Answer 1

这种算法最适合用递归吧

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"]

Answer 2

const data = {
  'A': {name：'A',parent:undefined},
  'AB':{name:'AB',parent:'A'},
  'AABA':{name:'AABA',parent:'AB'},
  ...
}

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

Answer 3

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"]

Answer 4

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"));