LeetCode算法题-Sum of Left Leaves(Java实现)

LeetCode算法题-Sum of Left Leaves(Java实现)

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

01 看题和准备

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

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

     3
    / \
   9  20
      / \
     15  7

本次解题使用的开发工具是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+篇,