【基础篇 - Day 15】 2023-02-27 - 129. 求根到叶子节点数字之和 （03. 树 ）

[threedayAAAAA]

给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。 每条从根节点到叶节点的路径都代表一个数字：

例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。 计算从根节点到叶节点生成的 所有数字之和 。

叶节点 是指没有子节点的节点。

 

示例 1：

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

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

提示：

树中节点的数目在范围 [1, 1000] 内 0 <= Node.val <= 9 树的深度不超过 10

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/sum-root-to-leaf-numbers 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[threedayAAAAA]

思路一

思路

层序遍历

代码

function sumNumbers(root: TreeNode | null): number {
    let result = 0
    if(!root){
        return result
    }
    let floor = [root]
    while(floor.length){
        let newFloor = []
        floor.forEach(item => {
            if(item.left) {
                item.left.val = item.val * 10 + item.left.val
                newFloor.push(item.left)
            }
            if(item.right) {
                item.right.val = item.val * 10 + item.right.val
                newFloor.push(item.right)
            } 
            if(item.left === null && item.right === null){
                result += item.val
            }
        })
        floor = newFloor
    }
    return result
};

时空复杂度

• 时间复杂度：O(N)
• 空间复杂度: O(logN)

思路二

思路

深序遍历

代码

function sumNumbers(root: TreeNode | null, sum = 0): number {
    if(!root || (!root.left && !root.right)){
        return sum + (root?.val ?? 0)
    }
    let result = 0
    if(root.left){
        result += sumNumbers(root.left, (sum + root.val) * 10) 
    }
    if(root.right){
        result += sumNumbers(root.right, (sum + root.val) * 10) 
    }
    return result
};

时空复杂度

• 时间复杂度：O(N)
• 空间复杂度： O(N)

[MiumMi]

思路

1. 子节点的值即为上一个节点*10 + 当前子节点的值

2. 根据以上分析，深度遍历二叉树，然后加上left和right节点的值即为最终值

   代码

   function sumNumbers(root: TreeNode | null, num: number = 0): number {
   if (!root) {
       return 0;
   }
   let total = num * 10 + root.val;
   if (!root.left && !root.right) {
       return total;
   }
   return sumNumbers(root.left, total) + sumNumbers(root.right, total);
   };

   ---

   分析

3. 时间复杂度：O(n)

4. 空间复杂度：O(n)

[yunliuyan]

思路

• bfs遍历

代码

function sumNumbers(root: TreeNode | null): number {
  let res = 0;
  const queue: TreeNode[] = [];
  if (root) {
    queue.push(root);
  }
  while(queue.length) {
    const curNode = queue.pop()!;
    // 叶节点则加入返回结果值
    if(!curNode?.left && !curNode?.right) {
      res += curNode.val;
    }
    if (curNode?.left) {
      // 左节点的值加上父节点的值
      curNode.left.val += curNode.val * 10;
      queue.push(curNode.left);
    }

    if(curNode.right) {
      // 右节点的值加上父节点的值
      curNode.right.val += curNode.val * 10;
      queue.push(curNode.right);
    }
  }
  return res;
};

复杂度分析

• 时间复杂度: O(n)
• 空间复杂度: O(n)