作者:LeetCode
链接:112. 路径总和
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
一、题目描述
给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。
说明:叶子节点是指没有子节点的节点。
示例:
给定如下二叉树,以及目标和sum = 22
:
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
返回true
, 因为存在目标和为 22 的根节点到叶子节点的路径5->4->11->2
。
二、题解
2.1 dfs深搜(递归)
算法:
利用递归深度优先搜索每个节点,每经过一个节点,sum值减去当前节点的值,继续搜索子节点。直到叶子节点的时候判断sum,为0返回true,否则返回false。
代码:
class Solution {
public:
bool hasPathSum(TreeNode* root, int sum) {
if (root == NULL) {
return false;
}
sum -= root->val;
// 搜索到叶子节点了
if (root->left == NULL && root->right == NULL) {
return sum == 0;
}
// 计算左右子节点
return hasPathSum(root->left, sum) || hasPathSum(root->right, sum);
}
};
复杂度分析
- 时间复杂度:我们访问每个节点一次,时间复杂度为O(N),其中N是节点个数。
- 空间复杂度:最坏情况下,整棵树是非平衡的,例如每个节点都只有一个孩子,递归会调用N次(树的高度),因此栈的空间开销是O(N) 。但在最好情况下,树是完全平衡的,高度只有 log(N),因此在这种情况下空间复杂度只有O(log(N)) 。
2.2 bfs广搜(迭代)
算法:
我们可以用栈将递归转成迭代的形式,深度优先搜索在除了最坏情况下都比广度优先搜索更快。最坏情况是指满足目标和的 root->leaf 路径是最后被考虑的,这种情况下深度优先搜索和广度优先搜索代价是相通的。
使用迭代的思路是:利用队列,每次保存当前节点以及剩余的sum,如果是叶子节点并且剩余的sum为0则返回true。否则,把节点的左右子节点分别压入队列,更新sum值。
所以我们从包含根节点的栈开始模拟,剩余目标和为 sum - root.val,然后开始迭代。弹出当前元素,如果当前剩余目标和为 0 并且在叶子节点上返回 True;如果剩余和不为零并且还处在非叶子节点上,将当前节点的所有孩子以及对应的剩余和压入栈中。
struct NodeSum {
TreeNode *node; // 当前节点
int sum; // 剩余的和
};
class Solution {
public:
bool hasPathSum(TreeNode* root, int sum) {
queue<NodeSum *> q;
NodeSum* p;
TreeNode *node;
int residualSum;
if (root == NULL) {
return false;
}
q.push(new NodeSum{ root, sum });
while (q.empty() == false) {
p = q.front();
q.pop();
node = p->node;
// 计算剩余需要的sum
residualSum = p->sum - node->val;
delete p;
// 存在左子节点,压入队列
if (node->left) {
q.push(new NodeSum{ node->left, residualSum });
}
// 存在右子节点,压入队列
if (node->right) {
q.push(new NodeSum{ node->right, residualSum });
}
// 叶子节点,sum为0
if (node->left == NULL && node->right == NULL && residualSum == 0) {
return true;
}
}
return false;
}
};
复杂度分析:
- 时间复杂度:和递归方法相同是O(N)。
- 空间复杂度:当树不平衡的最坏情况下是O(N) 。在最好情况(树是平衡的)下是 O(log(N))。
此处评论已关闭