【一天一大 lee】路径总和 II (难度:中等) - Day20200926

前端小书童

发布于 2020-09-29 20:17:26

3400

发布于 2020-09-29 20:17:26

文章被收录于专栏：前端小书童

题目:[1]

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。

示例:给定如下二叉树，以及目标和 sum = 22，

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

[
   [5,4,11,2],
   [5,8,4,5]
]

抛砖引玉

抛砖引玉

思路

递归回溯：在遍历子树时，可以选择右节点也可以选择左节点,那么在二叉树遍历的基础上再加上回溯的逻辑。

深度优先搜索（DFS）

DFS 模板：

function dfs(node) {
  if (node == null) return
  dfs(node.left)
  dfs(node.right)
}

题目要求记录的是从根节点到叶子节点的和满足条件,那么在遍历的工程中需要记录的值就包含：

遍历的节点 path（用于输出到结果数组）
遍历的选择的节点的和 num（用于校验是否满足条件）

回溯

路径回溯，回到上轮选择节点前，path.pop()
节点和回溯，回到上轮选择节点前的和

var pathSum = function(root, sum) {
  let _result = [],
    path = [],
    num = 0
  if (root === null) return _result
  function dfs(node) {
    if (node === null) return
    path.push(node.val)
    num = num + node.val
    if (node.left === null && node.right === null && num === sum) {
      _result.push([...path])
    }
    dfs(node.left)
    dfs(node.right)
    path.pop()
    num = num - node.val
  }
  dfs(root, 0)
  return _result
}

广度优先搜索（BFS）

BFS 模板：

function(root) {
  if (root == null) return
  let queue = [root]
  while(queue.length){
    let node = queue.pop();
    if(node.left) queue.push(node.left)
    if(node.right) queue.push(node.right)
  }
}

BFS 的逻辑可以不用回溯，直接正常遍历遍历到结束时如果有满足条件的路径就返回：

记录遍历过程中的节点和- queueSum
记录遍历的路径-map
- 使用哈希追溯父节点

var pathSum = function(root, sum) {
  let _result = [],
    map = new Map(),
    queueNode = [root],
    queueSum = [0]
  if (root === null) return []
  while (queueNode.length) {
    let node = queueNode.pop(),
      num = queueSum.pop() + node.val
    if (node.left == null && node.right == null) {
      // 满足要求，追溯父节点
      if (num == sum) getPath(node)
    } else {
      if (node.left != null) {
        map.set(node.left, node)
        queueNode.push(node.left)
        queueSum.push(num)
      }
      if (node.right != null) {
        map.set(node.right, node)
        queueNode.push(node.right)
        queueSum.push(num)
      }
    }
  }

  function getPath(node) {
    let temp = []
    while (node != null) {
      temp.push(node.val)
      node = map.get(node)
    }
    temp.reverse()
    _result.push(temp)
  }
  return _result.reverse()
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-09-28，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法