数据结构-根节点到叶子节点的路径（一）

dfs bfs 回溯算法

//案例
  var arr = [
    ["A", "B"],
    ["a", "b"],
    ["1", "2"]
  ]
  // =>
  // [
  //   'Aa1', 'Aa2',
  //   'Ab1', 'Ab2',
  //   'Ba1', 'Ba2',
  //   'Bb1', 'Bb2'
  // ]

1.1 bfs

 function bfs(arr){
    // 这道题本质是求根节点到叶子节点的路径
    // 思想
    // 根节点入列
    // 循环二叉树高度
    // 获取当前节点的长度 然后依次遍历
    let queue = []
    queue.push(['']) // 设置''为根节点 然后
    while(arr.length){
      let next = arr.shift()
      let length = queue.length
      for(let i = 0; i<length;i++){ // 当前层节点的长度
        let top = queue.shift() // 出列
        // 放入下轮的代码中
        for(let l of next){
          queue.push(top+l)
        }
      }
    }
    return queue
  }
  bfs(arr)

1.2 dfs

  function dfs(arr){
    let paths = []
    function temp(arr,index,path){
      if(arr[index]==undefined){
        paths.push(path)
        return
      }
      for(let i = 0; i<arr[index].length;i++){
        temp(arr,index+1,path+arr[index][i])
      }
    }
    temp(arr,0,'')
    console.log(paths)
  }
  dfs(arr)

1.3 dfs + 回溯

  // dfs + 回溯
  function dfsRecall(){
    let paths = []
    function temp(arr,index,sol){
      if(arr[index]==undefined){
        paths.push(sol.join(''))
        return
      }
      for(let i = 0; i<arr[index].length;i++){
        sol.push(arr[index][i])
        temp(arr,index+1,sol)
        sol.pop()
      }
    }
    temp(arr,0,[])
    console.log(paths)
  }
  dfsRecall(arr)

其实这道题就是求根节点到叶子节点的路径 不过是完全二叉树而已。