[LeetCode] Sum of Left Leaves 左子叶之和
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了[LeetCode] Sum of Left Leaves 左子叶之和，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2688字，纯文字阅读大概需要4分钟。
内容图文
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)) return0;
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) return0;
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)) return0;
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)) return0;
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 All in One 题目讲解汇总(持续更新中...)
原文：http://www.cnblogs.com/grandyang/p/5923559.html
内容总结
以上是互联网集市为您收集整理的[LeetCode] Sum of Left Leaves 左子叶之和全部内容，希望文章能够帮你解决[LeetCode] Sum of Left Leaves 左子叶之和所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。