leetcode 404. Sum of Left Leaves

404. Sum of Left Leaves:题目链接

DFS-递归

class Solution {
	// 时间复杂度O(N) 空间复杂度O(N):递归栈的大小
    // 递归宏观语义：返回以root为根的二叉树的左叶子结点之和
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left != null && root.left.left == null && root.left.right == null) {
            return root.left.val + sumOfLeftLeaves(root.right); // 如果不加sumOfLeftLeaves(root.right) 当满足上面条件时因为return结束了函数 根本就没有递归到右子树
        }
         // 二叉树的左叶子结点之和 = 左子树左叶子结点之和 + 有子树左叶子结点之和 
        return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
    }
}

BFS-层次遍历

class Solution {
    // BFS 时间复杂度O(N) 空间复杂度O(M):队列的大小
    public int sumOfLeftLeaves(TreeNode root) {
        int res = 0;
        if (root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode front = queue.poll();
            if (front.left!= null && front.left.left == null && front.left.right ==null) { // 左叶子结点
                res += front.left.val;
            }
            if (front.left != null) {
                queue.offer(front.left);
            }
            if (front.right != null) {
                queue.offer(front.right);
            }
        }
        return res;
    }
}