129. 求根节点到叶节点数字之和 🟨

题目

LeetCode 中等

给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字
例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
计算从根节点到叶节点生成的所有数字之和。
叶节点 是指没有子节点的节点。

示例
输入：root = [4,9,0,5,1]
输出：1026
解释：
从根到叶子节点路径 4->9->5 代表数字 495
从根到叶子节点路径 4->9->1 代表数字 491
从根到叶子节点路径 4->0 代表数字 40
因此，数字总和 = 495 + 491 + 40 = 1026

题解

方法：深度优先

深度优先 DFS 递归

时间复杂度：O(n)
空间复杂度：O(n)

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val
    this.left = left
    this.right = right
  }
}

function sumNumbers(root) {
  let sum = 0
  let path = []
  const dfs = root => {
    path.push(root.val)
    if (!root.left && !root.right) {
      sum += parseInt(path.join(''))

      console.log('到叶子节点', path, 'sum', sum)
    }
    if (root.left) dfs(root.left)
    if (root.right) dfs(root.right)
    path.pop()

    console.log('path after pop', path)
  }
  dfs(root)
  return sum
}

const tree = new TreeNode(4)
tree.left = new TreeNode(9, new TreeNode(5), new TreeNode(1))
tree.right = new TreeNode(0)

console.log('🌰', JSON.stringify(sumNumbers(tree)))

执行结果

到叶子节点 [4,9,5] sum 495
path after pop [4,9]
到叶子节点 [4,9,1] sum 986
path after pop [4,9]
path after pop [4]
到叶子节点 [4,0] sum 1026
path after pop [4]
path after pop []
🌰 1026

方法：广度优化

广度优化 BFS 队列

时间复杂度：O(n)
空间复杂度：O(n)

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val
    this.left = left
    this.right = right
  }
}

function sumNumbers(root) {
  if (root === null) {
    return 0
  }
  let sum = 0
  const nodeQueue = []
  const numQueue = []
  nodeQueue.push(root)
  numQueue.push(root.val)

  while (nodeQueue.length) {
    console.log(
      '♻️ nodeQueue',
      nodeQueue.map(n => n.val),
    )
    console.log('numQueue', numQueue)

    const node = nodeQueue.shift()
    const num = numQueue.shift()
    const left = node.left,
      right = node.right
    if (left === null && right === null) {
      sum += num
      console.log('🍃 到达叶子节点 node', node.val, 'sum', sum)
    } else {
      if (left !== null) {
        nodeQueue.push(left)
        numQueue.push(num * 10 + left.val)
      }
      if (right !== null) {
        nodeQueue.push(right)
        numQueue.push(num * 10 + right.val)
      }
    }
  }
  return sum
}

const tree = new TreeNode(4)
tree.left = new TreeNode(9, new TreeNode(5), new TreeNode(1))
tree.right = new TreeNode(0)

console.log('🌰', JSON.stringify(sumNumbers(tree)))

执行结果

♻️ nodeQueue [4]
numQueue [4]
♻️ nodeQueue [9,0]
numQueue [49,40]
♻️ nodeQueue [0,5,1]
numQueue [40,495,491]
🍃 到达叶子节点 node 0 sum 40
♻️ nodeQueue [5,1]
numQueue [495,491]
🍃 到达叶子节点 node 5 sum 535
♻️ nodeQueue [1]
numQueue [491]
🍃 到达叶子节点 node 1 sum 1026
🌰 1026

本页目录