求根节点到叶节点数字之和

给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。

每条从根节点到叶节点的路径都代表一个数字：

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

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

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

初始解法

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */
 
function sumNumbers(root: TreeNode | null): number {
    
    function recursion(node:TreeNode,path:number[],sum:number){
        //碰到叶子节点，开始求和
        if(node !==null && node.left === null && node.right === null){
            path.push(node.val)
            const current_number = +path.reduce((acc,curr)=>acc + `${curr}`,'')
            sum +=current_number
            //加完了，然后直接 path-1，return
            path.pop()
            return sum
        }
 
        //非叶子节点：加入 path，然后递归左子树/右子树
        let sum_left =0
        let sum_right = 0
        path.push(node.val)
        if(node.left)  {
            sum_left = recursion(node.left,path,sum)
        }
        if(node.right){
            sum_right = recursion(node.right,path,sum)
        }
        path.pop()
        return sum_left+sum_right
    }
    const path = []
    return recursion(root,path,0)
};

最好解法：数学递归法

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