404 左叶之和
小白翻译
给定二叉树的root，返回所有左叶的总和。
叶子是没有子节点的节点。左叶是另一个节点的左子节点的叶。
例子
小白教室做题
在大学某个自习的下午，小白坐在教室看到这道题。想想自己曾经和白月光做题，现在大过年的，也是只有自己练题了。左边一颗树，右边一棵树。。。
这时候黑长直女神过来问：小白，你复习到二叉树了吗，这道题你有什么思路啊？
小白内心镇定：这机会不就来了吗，小美，《飞驰人生2》有机会一起去看看吧？
哦，不是，咱们还是要干正事儿的，毕竟不能让小美失望啊。
这种题目我们首先把他进行下条件梳理。
- 树类的题目，首先我们要对树的结构有了解
- 另外，熟悉了算法后，我们对于Stack（栈）也要相对熟悉下，一般树的存储大都用到Queue或者Stack结构。
那么，对于这道题来说，也就是二左子树值的和，其实就是找每一层的左子树节点。我们可以考虑使用迭代（recursion）算法来实现问题。
其中，迭代算法的基本思路是：
- 使用栈来存储待遍历的节点。
- 从栈顶弹出节点，并判断该节点是否为左叶子节点，如果是则将该节点的值加入到结果中。
- 将该节点的左子树和右子树压入栈中。
小美：小伙子，可以啊，这不仅逻辑清晰，居然对于算法也是小有了解！不过电影票要你买单哦。
小白：没问题，谁叫为了“真爱
真正面试环节
面试官：咱们今天来个轻松的，你可以解答这道”除数游戏“的题目吗，来看看你对简单题目的理解。
小白：嘿嘿，这不巧了么这不是。
public int sumOfLeftLeaves(TreeNode root) {
if (root == null) {
return 0;
}
int sum = 0;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
// 判断当前节点是否为左叶子节点
if (node.left != null && node.left.left == null && node.left.right == null) {
sum += node.left.val;
}
// 将左子树和右子树压入栈中
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
return sum;
}
小明：OK，完事儿，等着面试官来表扬自己吧。他肯定会说：小子，你是个好手！工位都给你准备好了，工资你说了算。
面试官：矮油，不错啊，不过你这是不是有备而来啊，小伙子，迭代可有不少小伙伴都写的出来啊。你是否还有其他办法呢？
小明OS：今年这个找工市场，人言洛阳花似锦，偏我来时不逢春。。。不是，这方法按理说不错啊！面试官，其实我感觉树的话，也可以考虑递归的思想。
递归方法的核心思想是：
- 判断当前节点是否为左叶子节点，如果是则将该节点的值加入到结果中。
- 递归地遍历当前节点的左子树和右子树。
public int sumOfLeftLeaves(TreeNode root) {
if (root == null) {
return 0;
}
int sum = 0;
// 判断当前节点是否为左叶子节点
if (root.left != null && root.left.left == null && root.left.right == null) {
sum += root.left.val;
}
// 递归遍历左子树和右子树
sum += sumOfLeftLeaves(root.left);
sum += sumOfLeftLeaves(root.right);
return sum;
}
比较两者区别
迭代与递归算法都能正确地解决这道题，但它们的效率有所不同。
递归方法的效率较高，因为它只需要遍历一次二叉树。但是，递归方法的栈空间开销较大，在二叉树深度较大的情况下可能会导致栈溢出。
迭代方法的效率较低，因为它需要遍历两次二叉树。但是，迭代方法的栈空间开销较小，不会导致栈溢出。
小白：您好，面试官，这回可以了吧，我终于有钱请小美看电影了！
============================================================================
🍀🍀🍀🍀🍀🍀更多算法题解请看 面试数据结构与算法总结分类+leetcode目录【基础版】
编码道路漫漫，只要先看脚下的路，徐徐前进即可。