作者:LeetCode
链接:112. 路径总和
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
一、题目描述
给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。
说明:叶子节点是指没有子节点的节点。
示例:
给定如下二叉树,以及目标和sum = 22
:
1 2 3 4 5 6 7 |
5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1 |
返回true
, 因为存在目标和为 22 的根节点到叶子节点的路径5->4->11->2
。
二、题解
2.1 dfs深搜(递归)
算法:
利用递归深度优先搜索每个节点,每经过一个节点,sum值减去当前节点的值,继续搜索子节点。直到叶子节点的时候判断sum,为0返回true,否则返回false。
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
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;如果剩余和不为零并且还处在非叶子节点上,将当前节点的所有孩子以及对应的剩余和压入栈中。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
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))。
评论