leetCode ✏Leetcode基础刷题之(112. Path Sum)
✏描述
给定一棵二叉树和一个整数，判断是否存在从根结点到叶子结点值加起来等于给定值的路径。
✏题目实例
✏题目分析
只要使用深度优先算法思想遍历每一条完整的路径，如果是个空树直接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;
}
转载链接：https://leetcode.cn/
![[爱了]](/js/img/d1.gif)
![[尴尬]](/js/img/d16.gif)