112.md

✏️Leetcode基础刷题之(112. Path Sum)

2019-04-28 吴亲库里 库里的深夜食堂

---

✏️描述

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

---

✏️题目实例

​

✏️题目分析

只要使用深度优先算法思想遍历每一条完整的路径，如果是个空树直接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;
        
    }

联系

​