来个算法大佬看下这个问题?

Question

// 数据源
const arr = [{
  id: '1',
  children: [{
    id: '1.1',
    children: [{
      id: '1.1.1',
    }, {
      id: '1.1.2',
    }]
  }]
  }, {
  id: '2',
  children: [{
    id: '2.1',
  }, {
    id: '2.2',
    children: [{
      id: '2.2.1',
    }, {
      id: '2.2.2',
    }]
  }]
}]
const expandKeys = ['2.2.1','1.1.1']

我要把命中 expandKeys 的 item 以及 父级item 的 expand 设置为 true

期望的结果

const arr = [{
  id: '1',
  expand: true,
  children: [{
    id: '1.1',
    expand: true,
    children: [{
      id: '1.1.1',
      expand: true
    }, {
      id: '1.1.2',
    }]
  }]
  }, {
  id: '2',
  expand: true,
  children: [{
    id: '2.1',
  }, {
    id: '2.2',
    expand: true,
    children: [{
      id: '2.2.1',
      expand: true
    }, {
      id: '2.2.2',
    }]
  }]
}]

时间复杂度 最好 控制在 O(n^2)

Answer 1

// 数据源
    const arr = [{
      id: '1',
      children: [{
        id: '1.1',
        children: [{
          id: '1.1.1',
        }, {
          id: '1.1.2',
        }]
      }]
    }, {
      id: '2',
      children: [{
        id: '2.1',
      }, {
        id: '2.2',
        children: [{
          id: '2.2.1',
        }, {
          id: '2.2.2',
        }]
      }]
    }]
    const expandKeys = ['2.2.1', '1.1.1']
    
    function traversal (list) {
      if (!Array.isArray(list)) return
      
      let isExpanded = false
      list.forEach(item => {
        if (traversal(item.children) || expandKeys.includes(item.id)) {
          isExpanded = true
          item.isExpanded = true 
        }
      })
      
      return isExpanded
    }
    traversal(arr)

Answer 2

写了一个，允许任意层级，且只需遍历 expandKeys 中的节点（即，O(N) 算法）：

JavaScript 代码

let expandTree = (keys) => keys.reduce((o, s) => s.split('.').reduce((p, v, i, a) => p[a.slice(0, i+1).join('.')] ??= {}, o) && o, {});

let f = (keys, nodes) => Object.keys(keys).length && nodes?.forEach(i => {if (i.id in keys) {i.expand = true; f(keys[i.id], i.children)}});

使用

f(expandTree(['2.2', '2.2.1', '1.1.1']), arr)

结果

[
  {
    "id": "1",
    "children": [
      {
        "id": "1.1",
        "children": [
          {
            "id": "1.1.1",
            "expand": true
          },
          {
            "id": "1.1.2"
          }
        ],
        "expand": true
      }
    ],
    "expand": true
  },
  {
    "id": "2",
    "children": [
      {
        "id": "2.1"
      },
      {
        "id": "2.2",
        "children": [
          {
            "id": "2.2.1",
            "expand": true
          },
          {
            "id": "2.2.2"
          }
        ],
        "expand": true
      }
    ],
    "expand": true
  }
]

Answer 3

我觉得可以看这篇：javascript - 过滤/筛选树节点 - 边城客栈 - SegmentFault 思否

Answer 4

  const arr = [{
    id: '1',
    children: [{
      id: '1.1',
      children: [{
        id: '1.1.1',
      }, {
        id: '1.1.2',
      }]
    }]
  }, {
    id: '2',
    children: [{
      id: '2.1',
    }, {
      id: '2.2',
      children: [{
        id: '2.2.1',
      }, {
        id: '2.2.2',
      }]
    }]
  }]
  const expandKeys = ['2.2.1', '1.1.1']
  let fArr = []
  function expand (id, item) {
    if (item.id === id) {
      item.expand = true
      return
    }
    if (item.children) {
      for (let val of item.children) {
        expand(id, val)
      }
    }

  }

  // for (let key of expandKeys) {
  //   for (let item of arr) {
  //     expand(key, item)
  //   }
  // }



  for (let key of expandKeys) {
    let a = key.split('.')

    for (let item of arr) {
      let str = ''
      for (let i = 0; i < a.length; i++) {
        if (i == 0) {
          str = a[i] + ''
        } else {
          str = str + '.' + a[i]
        }
        expand(str, item)
      }
    }
  }

  console.log(arr);

Answer 5

function expand(arr,keys){
  for (let item of arr) {
    const index = keys.indexOf(item.id);
    if (index>=0){
      item.expand = true;
      keys.splice(index, 1);
    }else{
      item.expand = false;
    }
    if (item.children && item.children.length) {
      expand(item.children, keys);
    }
  }

  return arr;
}

const expandKeys = ['2','2.1','1.1.1'];
console.log(expand(arr, expandKeys));

Answer 6

写法有点粗糙，可以参考这个思路进行修改，js比较薄弱，不足请指正
const expandKeys = ['2.2.1','1.1.1'];
for (int i = 0;i< expandKeys.length; i++){

var strs = expandkeys[i].splice("."); //查找 2  2.2  2.2.1
for (int j = 0;j < strs[j].length ;j++){
    var matchStr += strs[i]; //拼装字符串
    //匹配id
    checkStr(matchStr);
}

}
//递归
function checkStr(String matchStr , Objects){
if(arr[k].id ==){

    arr[k].expand = true;

}

if(arr[k].childern){
    checkStr(matchStr,arr[k].childern);

}
}

Answer 7

function setNodeMark(arr) {
      arr.forEach(item => {
        if (item.children) {
          setNodeMark(item.children)
        }


        if (expandKeys.includes(item.id)) {
          item.expand = true
        }

        if(item.children && item.children.some(list => list.id.startsWith(item.id))) {
          item.expand = true
        }
      })

      return arr
    }
    let res = setNodeMark(arr)
    console.log(res);

递归搞定