深度优先和广度优先-技术圈

深度优先和广度优先

共 2458字，需浏览 5分钟

· 2022-04-14

路径总和

是否存在从当前节点 root 到叶子节点的路径，满足其路径和为 sum

let root = {  value: 5,  left: {    value: 4,    left: {      value: 11,      left: {        value: 7,        left: null,        right: null      },      right: {        value: 2,        left: null,        right: null      }    },    right: null  },  right: {    value: 8,    left: {      value: 13,      left: null,      right: null    },    right: {      value: 4,      left: null,      right: {        value: 1,        left: null,        right: null      }    }  }}

假定从根节点到当前节点的值之和为 val，我们可以将这个大问题转化为一个小问题：是否存在从当前节点的子节点到叶子的路径，满足其路径和为 sum - val。

// 深度优先function hasPathSum (root, sum) {  if (root == null) {    return false  }  if (root.left == null && root.right == null) {    return root.value === sum  }  return hasPathSum(root.left, sum - root.value) || hasPathSum(root.right, sum - root.value)}

广度优先

// 广度优先function hasPathSum (root, sum) {  if (root === null) {    return false  }  let node = [root]  let value = [root.value]  while (node.length) {    let now = node.shift()    let temp = value.shift()    if (temp === sum) {      return true    }    if (now.left && now.left !== null) {      node.push(now.left)      value.push(now.left.value + temp)    }    if (now.right && now.right !== null) {      node.push(now.right)      value.push(now.right.value + temp)    }  }  return false}

我们再看一个面试题，计算二叉树的所有路径。

// 深度优先function binaryTree (root) {  let paths = []  let construct_paths = (root, path) => {    if (root) {      path += root.value.toString()      if (root.left === null && root.right === null) {        paths.push(path)      } else {        // 当前节点不是叶子节点，继续递归        path += '->'        construct_paths(root.left, path)        construct_paths(root.right, path)      }    }  }  construct_paths(root, '')  return paths}// [ '5->4->11->7', '5->4->11->2', '5->8->13', '5->8->4->1' ]

广度优先

// 广度优先function binaryTree (root) {  if (root === null) {    return false  }  let node = [root]  let value = [root.value]  let paths = []  while (node.length) {    let now = node.shift()    let temp = value.shift()    if (now.left === null && now.right === null) {      paths.push(temp)    }    if (now.left && now.left !== null) {      node.push(now.left)      value.push(temp  + '->'+ now.left.value)    }    if (now.right && now.right !== null) {      node.push(now.right)      value.push(temp  + '->'+ now.right.value)    }  }  return paths}

这里在提一句，深度优先和广度优先的感念， “深度优先搜索就是树的先序遍历”，“广度优先搜索就是树的按层遍历”。