求教:js递归 树结构输出问题

seg2326
  • 76

数据源如:

<!DOCtype html>
<html lang="en-US">
<head>
    <title>demo</title>
</head>
<body>
  <script>
    const json = [
  {
      "id":4,
      "name":"标题1",
      "flag":0,
      "parentId":1,
      "children":[
          {
              "id":3,
              "name":"1-1",
              "flag":0,
              "parentId":4,
              "isLeaf": true,
              "children":null
          }
      ]
  },
  {
      "id":5,
      "name":"标题2",
      "flag":0,
      "parentId":1,
      "children":[
          {
              "id":4,
              "name":"2-1",
              "flag":0,
              "parentId":5,
              "isLeaf": true,
              "children":null
          },
          {
              "id":5,
              "name":"2-2",
              "flag":0,
              "parentId":5,
              "checked":true,
              "isLeaf": true,
              "children":null
          }
      ]
  },
  {
      "id":7,
      "name":"标题3",
      "flag":0,
      "parentId":1,
      "children":[
          {
              "id":6,
              "name":"3-1",
              "flag":0,
              "parentId":7,
              "children":[
                {
                  "id": 106,
                  "name": "3-1-1",
                  "checked": true,
                  "isLeaf": true,
                  "children": null,
                }
              ]
          }
      ]
  }
];
  function returnSelectedTree(list) {
    if (Array.isArray(list) && list.length !== 0) {
      list = list.map((item, index) => {
        // 哪裏有問題
        const children = !item.isLeaf ? item.children.filter(it => it.checked) : [];
        if (children.length > 0) {
          item = {...item, ...{children: children}};
        }
        if (!item.isLeaf) {
          returnSelectedTree(item.children)
        }
        return item;
      });
      return list;
    } else {
      return false;
    }
  }
  returnSelectedTree(json)
  console.log(returnSelectedTree(json));
</script>
</body>
</html>

选中子级别,将其父级输出,如图

选中2-2,输出 标题2的完整树结构,除过2-1;求N层级方法
即:排除未选择项,需要父级完整结构包含选择项。

想通過上面returnSelectedTree方法處理。。。

回复
阅读 970
2 个回答
type TreeNode = {
  id: number
  name: string
  flag: number
  parentId: number
  children: null | TreeNode[]
}

type TreeNodeWithExtraInfo = TreeNode & {
  __parent: TreeNodeWithExtraInfo | null
  __bitset: 0 | 1
  __subtreeBitSet: 0 | 1
  children: TreeNodeWithExtraInfo[] | null
}
type ID = number

const temp: TreeNode[] = [
  {
    id: 4,
    name: '标题1',
    flag: 0,
    parentId: 1,
    children: [{ id: 3, name: '1-12', flag: 0, parentId: 4, children: null }],
  },
  {
    id: 5,
    name: '标题2',
    flag: 0,
    parentId: 1,
    children: [
      { id: 4, name: '2-1', flag: 0, parentId: 5, children: null },
      { id: 6, name: '2-2', flag: 0, parentId: 5, children: null },
    ],
  },
  {
    id: 7,
    name: '标题3',
    flag: 0,
    parentId: 1,
    children: [
      { id: 8, name: '3-1', flag: 0, parentId: 7, children: null },
      { id: 9, name: '3-2', flag: 0, parentId: 7, children: null },
      { id: 10, name: '3-3', flag: 0, parentId: 7, children: null },
    ],
  },
]

const getSelectedSubtree = (nodes: TreeNode[], ids: ID[]): TreeNode[] => {
  const dummyRoot: TreeNodeWithExtraInfo = {
    children: nodes,
  } as any
  const idToNodeMap = new Map<ID, TreeNodeWithExtraInfo>()
  const ans: TreeNode = {
    children: [],
  } as any

  const proprocessNodes = (
    root: TreeNodeWithExtraInfo,
    parent: null | TreeNodeWithExtraInfo
  ): void => {
    if (parent) {
      root.__parent = parent
    }

    const children = root.children
    idToNodeMap.set(root.id, root)

    if (!children) return

    for (const node of children) {
      proprocessNodes(node, root)
    }
  }

  const markFlagFromSelectedNodeToRoot = (id: ID): void => {
    let node = idToNodeMap.get(id)!

    if (!node) {
      throw new Error('Not Implement')
    }

    let parent = node.__parent
    node.__bitset = 1

    while (parent) {
      parent.__subtreeBitSet |= node.__bitset | node.__subtreeBitSet

      node = parent
      parent = parent.__parent
    }
  }

  const bubbleProperties = (ids: ID[]) => {
    for (const id of ids) {
      markFlagFromSelectedNodeToRoot(id)
    }
  }

  const removeFlags = (node: TreeNodeWithExtraInfo): void => {
    node.__bitset = 0
    node.__subtreeBitSet = 0
  }

  const includeSomeFlags = (node: TreeNodeWithExtraInfo): boolean => {
    return (node.__bitset | node.__subtreeBitSet) !== 0
  }

  const dfs = (current: TreeNodeWithExtraInfo, workInProgress: TreeNode) => {
    if (!includeSomeFlags(current)) {
      return
    }

    const children = current.children

    if (!children) return

    for (const node of children) {
      const newNode: TreeNode = {
        ...node,
        children: [],
      }
      if (includeSomeFlags(node)) {
        workInProgress.children!.push(newNode)
        if (node.__subtreeBitSet) {
          dfs(node, newNode)
        }
      }
    }

    removeFlags(current)
  }

  proprocessNodes(dummyRoot, null)
  bubbleProperties(ids)
  dfs(dummyRoot, ans)

  return ans.children!
}

console.log(getSelectedSubtree(temp, [5, 10]))

可根据自己的业务逻辑添加二次查找时的优化逻辑以减少每次查询时预处理节点的逻辑的O(N)的时间复杂度

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
宣传栏