LeetCode算法题-Sum of Left Leaves（Java实现）

这是悦乐书的第217次更新，第230篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第85题（顺位题号是404）。找到给定二叉树中所有左叶的总和。例如：

二叉树中有两个左叶，分别为9和15。返回24。

本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。

02 第一种解法

使用递归。

特殊情况：当root为null时，直接返回0。

正常情况：定义一个变量sum来存每一次遇到左节点的累加和。如果当前节点的左节点不为空，则需要进一步判断该左节点自身有没有子节点，有子节点就继续调用方法本身，既没有左节点又没有右节点的时候，则将该节点值累加到sum上，接着使用当前节点的右节点继续调用自身，其返回的结果还是需要和sum累加，最后返回sum。

public int sumOfLeftLeaves(TreeNode root) {

    if (root == null) {

        return 0;

    }

    int sum = 0;

    if (root.left != null) {

        if (root.left.left == null && root.left.right == null) {

            sum += root.left.val;

        } else {

            sum += sumOfLeftLeaves(root.left);

        }

    }

    sum += sumOfLeftLeaves(root.right);

    return sum;

}

03 第二种解法

使用迭代的方法。

特殊情况：当root为null或者root没有子节点的时候，直接返回0。

正常情况：使用队列，先将root放入队列，然后开始循环，取出的当前节点的左节点不为空，就继续判断该左节点的左节点、右节点是不是都为空，如果都为空，就将该左节点的节点值累加进sum，如果不满足，则将其放入队列。如果当前节点的右节点不为空，则将其放入队列。这里的判断逻辑和上面递归方法是一致的。最后返回sum。

public int sumOfLeftLeaves2(TreeNode root) {

    int sum = 0;

    if (root == null) {

        return sum;

    }

    if (root.left == null && root.right == null) {

        return sum;

    }

    Queue<TreeNode> queue = new LinkedList<TreeNode>();

    queue.offer(root);

    while (!queue.isEmpty()) {

        TreeNode node = queue.poll();

        if (node.left != null) {

            if (node.left.left == null && node.left.right == null) {

                sum += node.left.val;

            } else {

                queue.offer(node.left);

            }

        }

        if (node.right != null) {

            queue.offer(node.right);

        }

    }

    return sum;

}

04 第三种解法

使用栈，思路和第二种解法一样。

public int sumOfLeftLeaves3(TreeNode root) {

    int sum = 0;

    if (root == null) {

        return sum;

    }

    if (root.left == null && root.right == null) {

        return sum;

    }

    Stack<TreeNode> stack = new Stack<TreeNode>();

    stack.push(root);

    while (!stack.isEmpty()) {

        TreeNode node = stack.pop();

        if (node.left != null) {

            if (node.left.left == null && node.left.right == null) {

                sum += node.left.val;

            } else {

                stack.push(node.left);

            }

        }

        if (node.right != null) {

            stack.push(node.right);

        }

    }

    return sum;

}

05 小结

算法专题目前已连续日更超过两个月，算法题文章85+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。

以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！

巴特西