129.md

✏️Leetcode基础刷题之(129. Sum Root to Leaf Numbers)

2019-08-21 吴亲库里 库里的深夜食堂

---

✏️描述

给定一个只包含0-9的二叉树。每一个根节点到叶子节点都代表着一个数字,求所有根节点到叶子节点的总和

---

✏️题目实例

​

✏️题目分析

既然是根节点到叶子节点这种一条路走到黑的形式当然是DFS来解了，不同的是，在demo中我们可以看到，每到一个新的节点，其实是把当前父节点的值乘以10倍再加上当前结点的。最终再把全部DFS不同的路径总和起来就是这道题的解

  /**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */
class Solution {

    /**
     * @param TreeNode $root
     * @return Integer
     */
    function sumNumbers($root) {
       return  $this->helper($root,0);
    }
    
    function helper($root,$num)
    {
        if(!$root) return 0;
        $num=$num*10+$root->val;
        if(!$root->left && !$root->right){
            return $num;
        }
        
       return  $this->helper($root->left,$num)+$this->helper($root->right,$num);
        
    }
}

这可是php啊，还需要*10这种操作吗，直接在后面拼上字符串不就行了，改一下。

    /**
     * @param TreeNode $root
     * @return Integer
     */
    function sumNumbers($root) {
       return  $this->helper($root,'');
    }
    
    function helper($root,$num)
    {
        if(!$root) return 0;
        $num .=$root->val;
        if(!$root->left && !$root->right){
            return $num;
        } 
       return  $this->helper($root->left,$num)+$this->helper($root->right,$num);
        
    }
}

---

联系

​