129. 求根到叶子节点数字之和（JS实现）

心已赠人 2023-03-04 08:13 4阅读 0赞

## 1 题目 ##

> 给定一个二叉树，它的每个结点都存放一个 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.

## 2 思路 ##

**这道题比较简单，直接用递归的方法深度遍历根节点到叶子节点的每条路径，并最后相加即可**

## 3代码 ##

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */
    /** * @param {TreeNode} root * @return {number} */
    var sumNumbers = function(root) { 
        if (!root) return 0;
        const result = [];
        function d(p, num) { 
            if (!p) return;
    
            num = num * 10 + p.val;
            if (!p.left && !p.right) { 
                result.push(num);
            } else { 
                d(p.left, num);
                d(p.right, num);
            }
        }
    
        d(root, 0);
    
        return result.reduce((a,b) => a+b);
    };