[LeetCode] Sum of Left Leaves 左子叶之和
Find the sum of all left leaves in a given binary tree.
Example:
3 / \ 9 20 / \ 15 7 There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.
这道题让我们求一棵二叉树的所有左子叶的和,那么看到这道题我们知道这肯定是考二叉树的遍历问题,那么最简洁的写法肯定是用递归,由于我们只需要累加左子叶之和,那么我们在进入递归函数的时候需要知道当前结点是否是左子节点,如果是左子节点,而且该左子节点再没有子节点了说明其是左子叶,那么我们将其值加入结果res中,我们用一个bool型的变量,如果为true说明当前结点是左子节点,若为false则说明是右子节点,不做特殊处理,整个来说就是个递归的先序遍历的写法,参见代码如下:
解法一:
class Solution { public: int sumOfLeftLeaves(TreeNode* root) { if (!root || (!root->left && !root->right)) return 0; int res = 0; helper(root->left, true, res); helper(root->right, false, res); return res; } void helper(TreeNode* node, bool left, int& res) { if (!node) return; if (!node->left && !node->right && left) res += node->val; helper(node->left, true, res); helper(node->right, false, res); } };
我们还可以写的更简洁一些,不需要写其他的函数,直接在原函数中检查当前节点的左子节点是否是左子叶,如果是的话,则返回左子叶的值加上对当前结点的右子节点调用递归的结果;如果不是的话,我们对左右子节点分别调用递归函数,返回二者之和,参见代码如下:
解法二:
class Solution { public: int sumOfLeftLeaves(TreeNode* root) { if (!root) return 0; if (root->left && !root->left->left && !root->left->right) { return root->left->val + sumOfLeftLeaves(root->right); } return sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right); } };
我们也可以使用迭代来解,因为这道题的本质是遍历二叉树,所以我们可以用层序遍历的迭代写法,利用queue来辅助,注意对左子叶的判断和处理,参见代码如下:
解法三:
class Solution { public: int sumOfLeftLeaves(TreeNode* root) { if (!root || (!root->left && !root->right)) return 0; int res = 0; queue<TreeNode*> q; q.push(root); while (!q.empty()) { TreeNode *t = q.front(); q.pop(); if (t->left && !t->left->left && !t->left->right) res += t->left->val; if (t->left) q.push(t->left); if (t->right) q.push(t->right); } return res; } };
我们也可以用stack来辅助,对比上面的解法,我们发现几乎一模一样,只是把queue换成了stack,但实际上遍历的顺序不同,这种方法是先序遍历的迭代写法,参见代码如下:
解法四:
class Solution { public: int sumOfLeftLeaves(TreeNode* root) { if (!root || (!root->left && !root->right)) return 0; int res = 0; stack<TreeNode*> s; s.push(root); while (!s.empty()) { TreeNode *t = s.top(); s.pop(); if (t->left && !t->left->left && !t->left->right) res += t->left->val; if (t->left) s.push(t->left); if (t->right) s.push(t->right); } return res; } };
参考资料:
https://discuss.leetcode.com/topic/60467/3-line-c-solution
https://discuss.leetcode.com/topic/60381/java-solution-using-bfs
https://discuss.leetcode.com/topic/60415/java-solution-with-stack
相关文章
- Leetcode: Sum of Left Leaves
- JS Leetcode 374. 猜数字大小 题解分析
- [LeetCode]Sum of Two Integers
- [LeetCode] Largest Number
- 【LeetCode】1. Two Sum
- Leetcode 236 Lowest Common Ancestor of a Binary Tree
- [LeetCode] 1326. Minimum Number of Taps to Open to Water a Garden 灌溉花园的最少水龙头数目
- [LeetCode] 1315. Sum of Nodes with Even-Valued Grandparent 祖父节点值为偶数的节点和
- [LeetCode] 1300. Sum of Mutated Array Closest to Target 转变数组后最接近目标值的数组和
- [LeetCode] 1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold 元素和小于等于阈值的正方形的最大边长
- [LeetCode] 1239. Maximum Length of a Concatenated String with Unique Characters 串联字符串的最大长度
- [LeetCode] 1074. Number of Submatrices That Sum to Target 元素和为目标值的子矩阵数量
- [LeetCode] 1155. Number of Dice Rolls With Target Sum 掷骰子的N种方法
- [LeetCode] 1020. Number of Enclaves 飞地的数量
- [LeetCode] 834. Sum of Distances in Tree 树中距离之和
- [LeetCode] 871. Minimum Number of Refueling Stops 最少的加油站个数
- [LeetCode] 856. Score of Parentheses 括号的分数
- [LeetCode] Binary Search 二分搜索法
- [LeetCode] Search in a Sorted Array of Unknown Size 在未知大小的有序数组中搜索
- [LeetCode] Set Intersection Size At Least Two 设置交集大小至少为2
- [LeetCode] Maximum Sum of 3 Non-Overlapping Subarrays 三个非重叠子数组的最大和
- [LeetCode] Max Area of Island 岛的最大面积
- [LeetCode] 633. Sum of Square Numbers 平方数之和
- [LeetCode] Subtree of Another Tree 另一个树的子树
- [LeetCode] Binary Tree Tilt 二叉树的坡度
- [LeetCode] 483. Smallest Good Base 最小的好基数
- [LeetCode] Reverse Vowels of a String 翻转字符串中的元音字母
- [LeetCode] Number of 1 Bits 位1的个数
- Leetcode——17. Letter Combinations of a Phone Number
- LeetCode 3. 无重复字符的最长子串
- leetcode 695. Max Area of Island 岛屿的最大面积(中等)