递归解法
思路
以为树天然就具有递归的特性,用递归方式是很容易想到的。遍历整棵树,如果点前是叶子结点(没有左右孩子),判断当前结点的值是否与$sum$相等,如果相等满足条件,返回$true$, 否者返回$false$。如果当前结点不是叶子结点,则递归调用$hasPathSum$函数,检查左右孩子是否满足条件,注意其中第二个参数为$sum$减去当前结点的值。
代码实现
class Solution {
public:
bool hasPathSum(TreeNode* root, int sum) {
if (root == nullptr ) return false;
if (root->left == nullptr && root->right == nullptr) {
return root->val == sum;
}
return hasPathSum(root->left, sum-root->val) || hasPathSum(root->right, sum-root->val);
}
};
复杂度分析
时间复杂度: $O(n)$, 需要访问每一个结点,所以时间复杂度为$O(n)$
空间复杂度: 最好情况,当树是完全二叉树时,递归的深度为$log(n)$, 所以最多需要$log(n)$的函数调用栈空间;最坏情况,当树退化为链表时,递归的深度为$n$, 需要$n$的函数调用中空间。
迭代解法
思路
其实和递归的思路一样,只不过递归是系统维护空间,而这里是自己维护栈空间。需要自定义一个栈,保存当前结点以及当前的$sum$。
代码实现
class Solution {
public:
bool hasPathSum(TreeNode* root, int sum) {
if (root == nullptr) return false;
stack<pair<TreeNode *, int>> __stack;
__stack.push(make_pair(root, sum));
while (!__stack.empty()) {
auto &item = __stack.top();
auto node = item.first;
sum = item.second;
__stack.pop();
if (node->left == nullptr && node->right == nullptr && node->val == sum) {
return true;
}
if (node->left) {
__stack.push(make_pair(node->left, sum - node->val));
}
if (node->right) {
__stack.push(make_pair(node->right, sum - node->val));
}
}
return false;
}
};
复杂度分析
时间复杂度: $O(n)$, 需要访问每一个结点,所以时间复杂度为$O(n)$
空间复杂度: 需要定义一个栈,最好情况,当树退化为链表时,栈中最多保存一个结点,空间复杂度为$O(1)$; 最好情况,当时完全二叉树时,栈中最多需要保存$log(n)$个结点,空间复杂度为$O(log(n))$.