css Audio - Active file-generic CSS - Active Generic - Active HTML - Active JS - Active SVG - Active Text - Active file-generic Video - Active header Love html icon-new-collection icon-person icon-team numbered-list123 pop-out spinner split-screen star tv

Pen Settings

CSS Base

Vendor Prefixing

Add External Stylesheets/Pens

Any URL's added here will be added as <link>s in order, and before the CSS in the editor. If you link to another Pen, it will include the CSS from that Pen. If the preprocessor matches, it will attempt to combine them before processing.

+ add another resource

You're using npm packages, so we've auto-selected Babel for you here, which we require to process imports and make it all work. If you need to use a different JavaScript preprocessor, remove the packages in the npm tab.

Add External Scripts/Pens

Any URL's added here will be added as <script>s in order, and run before the JavaScript in the editor. You can use the URL of any other Pen and it will include the JavaScript from that Pen.

+ add another resource

Use npm Packages

We can make npm packages available for you to use in your JavaScript. We use webpack to prepare them and make them available to import. We'll also process your JavaScript with Babel.

⚠️ This feature can only be used by logged in users.

Code Indentation

     

Save Automatically?

If active, Pens will autosave every 30 seconds after being saved once.

Auto-Updating Preview

If enabled, the preview panel updates automatically as you code. If disabled, use the "Run" button to update.

HTML Settings

Here you can Sed posuere consectetur est at lobortis. Donec ullamcorper nulla non metus auctor fringilla. Maecenas sed diam eget risus varius blandit sit amet non magna. Donec id elit non mi porta gravida at eget metus. Praesent commodo cursus magna, vel scelerisque nisl consectetur et.

            
              var data = [
  {
    key: 'one',
    value: '1',
    children: [
      {
        key: 'one-one',
        value: '1-1',
        children: [
          {
            key: 'one-one-one',
            value: '1-1-1'
          },
          {
            key: 'one-one-two',
            value: '1-1-2'
          }
        ]
      },
      {
        key: 'one-two',
        value: '1-2',
        children: [
          {
            key: 'one-two-one',
            value: '1-2-1'
          }
        ]
      },
    ]
  },
  {
    key: 'two',
    value: '2'
  },
  {
    key: 'three',
    value: '3',
    children: [
      {
        key: 'three-one',
        value: '3-1'
      },
      {
        key: 'three-two',
        value: '3-2',
        children: [
          {
            key: 'three-two-one',
            value: '3-2-1',
          },
          {
            key: 'three-two-two',
            value: '3-2-2'
          }
        ]
      }
    ]
  },
]

// 1. 深度优先遍历
function findPathDFS(source, goal) {
  //  把所有资源放到一个树的节点下,因为会改变原数据,因此做深拷贝处理
  var dataSource = [{children: JSON.parse(JSON.stringify(source))}]
  var res = []
  return (function dfs(data) {
    if (!data.length) return res
    res.push(data[0])
    // 深度搜索一条数据,存取在数组 res 中
    if (data[0].children) return dfs(data[0].children)
    // 匹配成功
    if (res[res.length - 1].value === goal) {
      // 删除自己添加树的根节点
      res.shift()
      return res.map(r => r.key)
    }
    // 匹配失败则删掉当前比对的节点
    res.pop()
    // 没有匹配到任何值则 return
    if (!res.length) return res
    // 取得最后一个节点,待做再次匹配
    var lastNode = res[res.length - 1]
    // 删除已经匹配失败的节点(即为上面 res.pop() 的内容)
    lastNode.children.shift()
    // 没有 children 时
    if (!lastNode.children.length) {
      // 删除空 children,且此时需要深度搜索的为 res 的最后一个值
      delete lastNode.children
      return dfs([res.pop()])
    }
    return dfs(lastNode.children)
  })(dataSource)
}

// 1.1 优化后的深度搜索
function findPathDFS2(source, goal) {
  // 因为会改变原数据,因此做深拷贝处理
  var dataSource = JSON.parse(JSON.stringify(source))
  var res = []
  return (function dfs(data) {
    res.push(data)
    // 深度搜索一条数据,存取在数组 res 中
    if (data.children) return dfs(data.children[0])
    // 匹配成功
    if (res[res.length - 1].value === goal) {
      return res.map(r => r.key)
    }
    // 匹配失败则删掉当前比对的节点
    res.pop()
    // 没有匹配到任何值则 return,如果源数据有值则再次深度搜索
    if (!res.length) return !!dataSource.length ? dfs(dataSource.shift()) : res
    // 取得最后一个节点,待做再次匹配
    var lastNode = res[res.length - 1]
    // 删除已经匹配失败的节点(即为上面 res.pop() 的内容)
    lastNode.children.shift()
    // 没有 children 时
    if (!lastNode.children.length) {
      // 删除空 children,且此时需要深度搜索的为 res 的最后一个值
      delete lastNode.children
      return dfs(res.pop())
    }
    return dfs(lastNode.children[0])
  })(dataSource.shift())
}

// 2. 广度优先遍历
function findPathBFS(source, goal) {
  // 深拷贝原始数据
  var dataSource = JSON.parse(JSON.stringify(source))
  var res = []
  // 每一层的数据都 push 进 res
  res.push(...dataSource)
  // res 动态增加长度
  for (var i = 0; i < res.length; i++) {
    var curData = res[i]
    // 匹配成功
    if (curData.value === goal) {
      var result = []
      // 返回当前对象及其父节点所组成的结果
      return (function findParent(data) {
        result.unshift(data.key)
        if (data.parent) return findParent(data.parent)
        return result
      })(curData)
    }
    // 如果有 children 则 push 进 res 中待搜索
    if (curData.children) {
      res.push(...curData.children.map(d => {
        // 在每一个数据中增加 parent,为了记录路径使用
        d.parent = curData
        return d
      }))
    }
  }
  // 没有搜索到结果,默认返回空数组
  return []
}

var res = findPathBFS(data, '3-2-2')
console.log('done: ', res)
            
          
!
999px
🕑 One or more of the npm packages you are using needs to be built. You're the first person to ever need it! We're building it right now and your preview will start updating again when it's ready.
Loading ..................

Console