递归解法
问:能否缩小规模,问题不变?
答:设从根到当前节点的和为val,则是否存在从当前节点到叶节点的路径和为:sum - val,该问题和原问题等价,且缩小了规模。
class Solution {
public:
bool hasPathSum(TreeNode *root, int sum) {
if (root == NULL) return false;//root空则返回假
if (root->left == NULL && root->right == NULL) {//若当前节点左右节点都空
return sum == root->val;//则判断sum是否和root->val相等,因sum每过一个节点就被减掉一个值
}
return hasPathSum(root->left, sum - root->val) ||
hasPathSum(root->right, sum - root->val);//递归左右节点,每过一个节点就从sum里减去当前节点的值
}
};
队列解法
用两个队列,保持出队顺序相同,这个技巧等同用2个数组分别表示下标和值的思路。
class Solution{
public:
bool hasPathSum(TreeNode *root,int sum){
if(root==NULL) return false;//如果root空则返回假
queue<TreeNode*> q;//定义存放节点的队列
queue<int> qval;//定义存放节点值的队列,这两个队列保持同样的顺序,保证对应的节点和值同时出队
q.push(root);//把当前节点放入q
qval.push(root->val);//把当前节点值放入qval,两个队列保持同步
while(!q.empty()){//队列q不空循环
TreeNode *u=q.front();//保存q队头
int v=qval.front();//保存qval队头
q.pop();//弹出
qval.pop();//弹出
if(u->left==NULL && u->right==NULL){//如果当前节点的左右子节点都空
if(v==sum) return true;//如果v等于目标值返回真
continue;//否则下一次循环
}
if(u->left!=NULL){//如果u左节点不空
q.push(u->left);//放入u的左节点到队列q
qval.push(u->left->val+v);//放入u的左节点的值到队列qval
}
if(u-right!=NULL){//如果u右节点不空
q.push(u->right);//放入u右节点到队列q
qval.push(u->right->val+v);//放入u右节点的值到队列qval
}
}
return false;//若循环结束,则返回假
}
};