【Day 15】 求根到叶子节点数字之和

题目描述

给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。

例如，从根到叶子节点路径 1->2->3 代表数字 123。

计算从根到叶子节点生成的所有数字之和。

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

示例 1:

输入: [1,2,3]
1
/ \
 2 3
输出: 25
解释:
从根到叶子节点路径 1->2 代表数字 12.
从根到叶子节点路径 1->3 代表数字 13.
因此，数字总和 = 12 + 13 = 25.
示例 2:

输入: [4,9,0,5,1]
4
/ \
 9 0
/ \
5 1
输出: 1026
解释:
从根到叶子节点路径 4->9->5 代表数字 495.
从根到叶子节点路径 4->9->1 代表数字 491.
从根到叶子节点路径 4->0 代表数字 40.
因此，数字总和 = 495 + 491 + 40 = 1026.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sum-root-to-leaf-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的回答

解法一

时间复杂度 O(n)

var sumNumbers = function (root) {
    let sum = 0
    function dfs(root, cur) {
        if (!root) return
        let cursum = cur * 10 + root.val
        if (!root.left && !root.right) {
            sum += cursum
            return
        }
        dfs(root.left, cursum)
        dfs(root.right, cursum)
    }
    dfs(root, 0)
    return sum
};

参考回答

DFS

求从根到叶子的路径之和，那我们只需要把每条根到叶子的路径找出来，并求和即可，这里用 DFS 去解，DFS 也是最容易想到的

function sumNumbers1(root) {
  let sum = 0;
  function dfs(root, cur) {
    if (!root) {
      return
    }
    let curSum = cur * 10 + root.val
    if (!root.left && !root.right) {
      sum += curSum
      return
    }
    dfs(root.left, curSum)
    dfs(root.right, curSum)
  }
  dfs(root, 0)
  return sum
}

BFS

如果说 DFS 是孤军独入，取敌将首级，那么 BFS 就是堂堂正正，车马摆开，层层推进。BFS 可能没那么优雅，但是掌握模板之后简直就是神器。

要求根到的叶子的路径的和，那我们把中间每一层对应的值都求出来，当前层的节点是叶子节点，把对应值相加即可

function sumNumbers(root) {
  let sum = 0
  let curLevel = []
  if (root) {
    curLevel.push(root)
  }
  while(curLevel.length) {
    let nextLevel = []
    for (let i = 0; i < curLevel.length; i++) {
      let cur = curLevel[i]
      if (cur.left) {
        cur.left.val = cur.val * 10 + cur.left.val
        nextLevel.push(cur.left)
      }
      if (cur.right) {
        cur.right.val = cur.val * 10 + cur.right.val
        nextLevel.push(cur.right)
      }
      if (!cur.left && !cur.right) {
        sum += cur.val
      }
      curLevel = nextLevel
    }
  }
  return sum
}

先序遍历

从树根开始先序遍历，用一个变量 curSum 跟踪到当前节点为止的根到节点组成数字，在当前节点更新 curSum

function sumNumbers(root) {
  return preorder(root, 0)
}

function preorder(root, curSum) {
  if (root === null) {
    return 0
  }
  curSum = root.val + curSum * 10
  if (!root.left && !root.right) {
    return curSum
  }
  return preorder(root.left, curSum) + preorder(root.right, curSum)
}