Leetcode基础刷题之PHP解析(112. Path Sum)

2019-4-28 星期天  开始吧

上一题链接 Leetcode基础刷题之PHP解析(268. Missing Number)

题目描述

给定一棵二叉树和一个整数，判断是否存在从根结点到叶子结点值加起来等于给定值的路径。

题目分析

只要使用深度优先算法思想遍历每一条完整的路径，如果是个空树直接false，如果结点没有左右子树(说明此时已然是叶子结点，判断值是否是给定值，这个条件正好是递归终止的条件)，相等直接返回true，根据这个推导出递归公式。

 /**
     * @param TreeNode $root
     * @param Integer $sum
     * @return Boolean
     */
    function hasPathSum($root, $sum) {
         if($root==null){
             return false;
         }
         if($root->left ==null && $root->right==null && $root->val==$sum) return true;
         return $this->hasPathSum($root->left,$sum-$root->val) || $this->hasPathSum($root->right,$sum-$root->val);
       
    }

当然也可以迭代来解

/**
     * @param TreeNode $root
     * @param Integer $sum
     * @return Boolean
     */
    function hasPathSum($root, $sum) {
        if($root==null){
            return false;
        }
        $res=[];
        array_push($res,$root);
        while(!empty($res)){
            $node=array_shift($res);
            if(!$node->left && !$node->right ){
                if($node->val==$sum) return true;
            }
            
            if($node->left){
                $node->left->val +=$node->val;
                array_push($res,$node->left);
            }
            if($node->right){
                $node->right->val +=$node->val;
                array_push($res,$node->right);
            }
        }
        return false;
        
    }

Github整理地址：https://github.com/wuqinqiang/leetcode-php