随州网站建设有限公司,网站建设 电子政务,南宁网站建设业务员,今天郴州刚刚发生的事404. 左叶子之和 文章目录 [404. 左叶子之和](https://leetcode.cn/problems/sum-of-left-leaves/)一、题目二、题解方法一#xff1a;递归方法二#xff1a;迭代 一、题目
给定二叉树的根节点 root #xff0c;返回所有左叶子之和。
示例 1#xff1a; 输入: root [3,9…404. 左叶子之和 文章目录 [404. 左叶子之和](https://leetcode.cn/problems/sum-of-left-leaves/)一、题目二、题解方法一递归方法二迭代 一、题目
给定二叉树的根节点 root 返回所有左叶子之和。
示例 1 输入: root [3,9,20,null,null,15,7]
输出: 24
解释: 在这个二叉树中有两个左叶子分别是 9 和 15所以返回 24示例 2:
输入: root [1]
输出: 0提示:
节点数在 [1, 1000] 范围内-1000 Node.val 1000
二、题解
方法一递归
算法思路
题目要求计算二叉树中所有左叶子节点的值之和。我们可以使用递归来解决这个问题。递归的思想是对于每个节点我们判断它是否是左叶子节点如果是则将其值加到结果中然后递归地处理它的左子树和右子树。
具体实现 我们首先定义一个变量 sum 来保存左叶子节点值的和并初始化为0。 在递归函数 sumOfLeftLeaves 中我们首先检查当前节点是否为空如果为空则返回0。 然后我们检查当前节点的左子节点是否存在以及左子节点是否为叶子节点。如果是叶子节点则将其值加到 sum 中。 最后我们递归地处理当前节点的左子树和右子树将它们的返回值累加到 sum 中。 在每一层递归结束后函数返回当前子树中左叶子节点的值之和。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {int sum 0;if (root nullptr) {return 0;}// 判断左子节点是否为叶子节点如果是则将值加入 sumif (root-left !root-left-left !root-left-right) {sum root-left-val;}// 递归处理左子树和右子树并累加结果到 sumreturn sum sumOfLeftLeaves(root-left) sumOfLeftLeaves(root-right);}
};算法分析 时间复杂度遍历整个二叉树的时间复杂度为 O(N)其中 N 是二叉树的节点数。在每个节点上我们进行常数时间的判断和加法操作。 空间复杂度递归函数的调用会占用栈空间递归的深度最坏情况下为树的高度所以空间复杂度为 O(H)其中 H 是二叉树的高度。在最坏情况下二叉树可能退化为链表高度为 N此时空间复杂度为 O(N)。但在一般情况下二叉树的高度平衡空间复杂度会接近 O(logN)。
方法二迭代
算法思路
我们可以使用深度优先搜索DFS来遍历二叉树使用栈来辅助遍历。在遍历的过程中对于每个节点我们检查它的左子节点是否存在如果存在继续检查左子节点是否为叶子节点即没有左右子节点。如果是叶子节点则将其值加到累加器 sum 中。对于非叶子节点我们将左子节点压入栈以便后续继续检查。然后无论是否有右子节点都将右子节点压入栈以确保我们遍历了所有可能的路径。
具体实现
class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {stackTreeNode* st;int sum 0;if (root nullptr) {return 0;}st.push(root);while (!st.empty()) {TreeNode* node st.top();st.pop();if (node-left) {if (!node-left-left !node-left-right) {sum node-left-val; // 如果左子节点是叶子节点将值加入 sum} else {st.push(node-left); // 如果左子节点不是叶子节点将左子节点压入栈}}if (node-right) {st.push(node-right); // 将右子节点压入栈无论是否为叶子节点}}return sum;}
};算法分析
时间复杂度遍历整个二叉树的时间复杂度为 O(N)其中 N 是二叉树的节点数。在每个节点上我们进行常数时间的判断、加法和栈操作。空间复杂度使用了一个栈来辅助遍历栈的空间占用与二叉树的高度相关最坏情况下为 O(N)。因此总体空间复杂度为 O(N)。
