Leetcode基础刷题之PHP解析(129. Sum Root to Leaf Numbers）

Created 5 years ago by 吴亲库里, Updated 5 years ago Revision #1 2343 views 1 likes 0 collects

2019-8-21 星期三开始吧

上一题链接Leetcode基础刷题之PHP解析(128. Longest Consecutive Sequence)

题目描述

给定一个只包含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);
        
    }
}

看下ac完全没问题