Pen Settings

HTML

CSS

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

JavaScript

Babel is required to process package imports. If you need a different preprocessor remove all packages first.

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

Behavior

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.

Format on Save

If enabled, your code will be formatted when you actively save your Pen. Note: your code becomes un-folded during formatting.

Editor Settings

Code Indentation

Want to change your Syntax Highlighting theme, Fonts and more?

Visit your global Editor Settings.

HTML

              
                
              
            
!

CSS

              
                
              
            
!

JS

              
                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

Console