解题思路

本题使用 $DFS$ 算法和字符串加法。

先根据层序遍历输入建立二叉树，其中 $null$ 表示空节点。

遍历二叉树时，维护当前从根节点到当前节点的路径字符串 $path$。

当遍历到叶子节点时，说明找到了一条完整路径。此时将 $path$ 反转，就可以得到从叶子节点到根节点组成的数字。

题目描述

给定一棵二叉树，树中每个节点都包含一个数字，数字范围为 $0$ 到 $9$。

从每个叶子节点出发，沿着路径一直走到根节点，可以组成一个数字。路径上的节点值按照从叶子节点到根节点的顺序依次拼接。

请你计算所有叶子节点到根节点路径组成的数字之和。

输入描述

输入一行，表示二叉树的层序遍历结果。

节点值之间用空格分隔。

如果某个节点为空，用 $null$ 表示。

输出描述

输出一个整数，表示所有叶子节点到根节点路径组成的数字之和。

样例 $1$

输入

4 9 0 5 1

输出

792

样例解释

二叉树结构如下：

      4
     / \
    9   0
   / \
  5   1

所有叶子节点到根节点的路径为：

• $5 -> 9 -> 4$，组成数字 $594$
• $1 -> 9 -> 4$，组成数字 $194$
• $0 -> 4$，组成数字 $04$，也就是 $4$

所以答案为：

594 + 194 + 4 = 792

数据范围

• 节点个数为 $n$
• $1 <= n <= 10^4$
• 每个节点的值都在 $0$ 到 $9$ 之间
• 输入保证是一棵合法的二叉树层序遍历结果