js递归问题

Question

请问如下需求如何实现:

const data = {
    id: '1',
    children: [{
            id: '11',
            children: [{
                    id: '111'
                },
                {
                    id: '112',
                    children: []
                }
            ]
        },
        {
            id: '12',
            children: [{
                id: '121',
                children: [{
                    id: '1211',
                    children: []
                }]
            }]
        }
    ]
}

getPath(data, '112') //  ==>  ['1','11','112']

getPath(data, '1211') //  ==>  ['1','12','121','1211']

Answer 1

深度优先搜索

const getPath = (data, id) => {
    const results = [];
    const DFS = (data, id, list) => {
        list.push(data.id);
        if (id === data.id) return true;
        if (data.children) {
            const { children } = data;
            for (const child of children) {
                const hasResult = DFS(child, id, list);
                if (hasResult) return true;
            }
            list.pop();
        } else {
            list.pop();
        }
    }
    DFS(data, id, results);
    return results;
}

Answer 2

function getPath(data, id) {
    const result = [];
    for (let i = 1; i <= id.length; i++) {
        result.push(id.substring(0, i));
    }
    return result;
}

function getPath(data, id) {
    //错误判断
    if (!data || !id) return false;
    //终止条件
    if (data.id == id) return [id];
    //记录
    let result = false;
    //递归
    if (data.children && data.children.length) {
        data.children.some(child => {
            result = getPath(child, id);
            return result;
        });
    }
    return result ? [data.id, ...result] : false;
}

Answer 3

var newarr = []
function render (arr, newarr, str) {
        let i = 0
        let len = arr.length
        for (;i < len; i++) {
          if (str.indexOf(arr[i].id) != -1){
            newarr.push({id: arr[i].id})
          }
          if (arr[i].children && arr[i].children.length > 0) {
            render(arr[i].children, newarr, str)
          }
        }
        return newarr
      }
render(data,newarr,'1211')
console.log(newarr)

和你的要求还有点瑕疵，可以自己修改一下

Answer 4

function getPath(obj,id,ans=[]){

    if(obj.id===id){
        ans.push(obj.id);
        return ans;
    }
    else if (obj.children&&obj.children.length>0){
        for(let child of obj.children){
            let childAns=ans.concat();//深克隆数组
            childAns.push(obj.id);
            let res=getPath(child,id,childAns);
            if(res){
                return res;
            }
        }
    }
}

Answer 5

function getData(data, id) {
            let arr = [];
            let len = 1;
            let cb = function (data) {
                let firstId = id.substr(0, len);
                if (data.id === firstId) {
                    arr.push(data.id);
                    len++;
                    if (data.children && data.children.length > 0) {
                        for (let i = 0; i < data.children.length; i++) {
                            let item = data.children[i];
                            cb(item)
                        }
                    }
                }
            }
            cb(data)
            return arr
        }

Answer 6

let result = []

function getPath(source, key) {
  for (let item of source) {
    if (item.id == key) {
      result.unshift(item.id)
      return true
    } else if (item.children && item.children.length > 0 && getPath(item.children, key)) {
      result.unshift(item.id)
       return true
    }
  }

  return false
}

getPath([data], '121')


console.log(result)