小白水平理解面试经典题目LeetCode 404 Sum of Left Leaves【Tree】-Toy模板网

这篇具有很好参考价值的文章主要介绍了小白水平理解面试经典题目LeetCode 404 Sum of Left Leaves【Tree】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

404 左叶之和

小白翻译

给定二叉树的root，返回所有左叶的总和。
叶子是没有子节点的节点。左叶是另一个节点的左子节点的叶。

例子

小白水平理解面试经典题目LeetCode 404 Sum of Left Leaves【Tree】,leetcode,面试,leetcode,职场和发展,算法

小白教室做题

在大学某个自习的下午，小白坐在教室看到这道题。想想自己曾经和白月光做题，现在大过年的，也是只有自己练题了。左边一颗树，右边一棵树。。。

这时候黑长直女神过来问：小白，你复习到二叉树了吗，这道题你有什么思路啊？

小白内心镇定：这机会不就来了吗，小美，《飞驰人生2》有机会一起去看看吧？
小白水平理解面试经典题目LeetCode 404 Sum of Left Leaves【Tree】,leetcode,面试,leetcode,职场和发展,算法
哦，不是，咱们还是要干正事儿的，毕竟不能让小美失望啊。

这种题目我们首先把他进行下条件梳理。

树类的题目，首先我们要对树的结构有了解
另外，熟悉了算法后，我们对于Stack（栈）也要相对熟悉下，一般树的存储大都用到Queue或者Stack结构。

那么，对于这道题来说，也就是二左子树值的和，其实就是找每一层的左子树节点。我们可以考虑使用迭代（recursion）算法来实现问题。

其中，迭代算法的基本思路是：

使用栈来存储待遍历的节点。
从栈顶弹出节点，并判断该节点是否为左叶子节点，如果是则将该节点的值加入到结果中。
将该节点的左子树和右子树压入栈中。

小美：小伙子，可以啊，这不仅逻辑清晰，居然对于算法也是小有了解！不过电影票要你买单哦。

小白：没问题，谁叫为了“真爱
小白水平理解面试经典题目LeetCode 404 Sum of Left Leaves【Tree】,leetcode,面试,leetcode,职场和发展,算法

真正面试环节

面试官：咱们今天来个轻松的，你可以解答这道”除数游戏“的题目吗，来看看你对简单题目的理解。

小白：嘿嘿，这不巧了么这不是。

小白水平理解面试经典题目LeetCode 404 Sum of Left Leaves【Tree】,leetcode,面试,leetcode,职场和发展,算法

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，完事儿，等着面试官来表扬自己吧。他肯定会说：小子，你是个好手！工位都给你准备好了，工资你说了算。

面试官：矮油，不错啊，不过你这是不是有备而来啊，小伙子，迭代可有不少小伙伴都写的出来啊。你是否还有其他办法呢？

小白水平理解面试经典题目LeetCode 404 Sum of Left Leaves【Tree】,leetcode,面试,leetcode,职场和发展,算法

小明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 404 Sum of Left Leaves【Tree】,leetcode,面试,leetcode,职场和发展,算法

============================================================================
🍀🍀🍀🍀🍀🍀更多算法题解请看面试数据结构与算法总结分类+leetcode目录【基础版】
编码道路漫漫，只要先看脚下的路，徐徐前进即可。文章来源地址https://www.toymoban.com/news/detail-836080.html

到了这里，关于小白水平理解面试经典题目LeetCode 404 Sum of Left Leaves【Tree】的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！