LeetCode日记–404.Sum of left leaves

发布于 2020-09-19  110 次阅读


碎碎念时间:感觉一天做一道完全不够啊,自己还是太垃圾了,尽量一天两道吧!

题目如下:

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.

这道题真的很简单,不过好久没写树相关的东西了,就写一道练练手吧!

思路:

既然是找左子叶的个数,那么这样的节点就有两个条件,其一这必须是个叶子,其二这必须在左边。

剩下的就是考虑遍历的方法,遍历方法就是DFS(Deepth-First-Search)或者是BFS(Breadth-First-Search)两种。深度优先基本上是使用递归沿着一个节点一直往下刨,广度优先则是使用迭代的方法按顺序搜(使用一个queue装节点,每搜到一个节点就往队列里面丢)。

那么下面分别写出DFS和BFS的代码。

DFS:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        return root!=null?dfs(root):0;
    }
    int dfs(TreeNode node){
        int res = 0;
        if(node.left!=null)
            res += isLeaves(node.left)?node.left.val:dfs(node.left);
        if(node.right!=null)
            res += isLeaves(node.right)?0:dfs(node.right);
        return res;
    }
    boolean isLeaves(TreeNode node){
        if( node.left==null && node.right==null)
            return true;
        else
            return false;
    }
}

BFS:

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        int ans = 0;
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.left != null) {
                if (isLeafNode(node.left)) {
                    ans += node.left.val;
                } else {
                    queue.offer(node.left);
                }
            }
            if (node.right != null) {
                if (!isLeafNode(node.right)) {
                    queue.offer(node.right);
                }
            }
        }
        return ans;
    }

    public boolean isLeafNode(TreeNode node) {
        return node.left == null && node.right == null;
    }
}

小声逼逼环节:

其实我原以为DFS的内存开销会大于BFS比较多的,但是似乎并没有。而且不知道为什么DFS在时间开销上表现也比BFS好。


你好哇!欢迎来到雷公马碎碎念的地方:)