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


2019-8-21 星期三 开始吧

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

61713f5b809ddd42ef3734168982f6bd.png


题目描述

给定一个只包含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完全没问题u1F602.png?tp=webp&wxfrom=5&wx_lazy=1&wx_co=1
8f7253f7e9556f689206d61ca225490c.png
这里使用的是递归,你可以试着咋么使用迭代的方式实现.


点赞 取消点赞 收藏 取消收藏

<< 上一篇: Leetcode基础刷题之PHP解析(128. Longest Consecutive Sequence)

>> 下一篇: Leetcode基础刷题之PHP解析(130. Surrounded Regions)