【力扣题解】P404-左叶子之和-Java题解

花无缺

👨‍💻博客主页：@花无缺
欢迎点赞👍 收藏⭐ 留言📝 加关注✅!
本文由 花无缺 原创

收录于专栏【力扣题解】

文章目录

【力扣题解】P404-左叶子之和-Java题解
- 🌏题目描述
- 💡题解
- 🌏总结

【力扣题解】P404-左叶子之和-Java题解

P404.左叶子之和

🌏题目描述

给定二叉树的根节点 root ，返回所有左叶子之和。

示例 1：

在这里插入图片描述

输入: root = [3,9,20,null,null,15,7] 
输出: 24 
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

示例 2:

输入: root = [1]
输出: 0

提示:

节点数在 [1, 1000] 范围内
-1000 <= Node.val <= 1000

💡题解

深度优先搜索：

public int sumOfLeftLeaves(TreeNode root) {
    return root == null ? 0 : dfs(root);
}
// 深度优先搜索
public static int dfs(TreeNode node) {
    int res = 0;
    // 递归搜索左子树
    if (node.left != null) {
        // 如果当前左子树是叶子节点就累加节点值
        // 如果不是叶子节点就继续递归遍历该节点
        res += isLeafNode(node.left) ? node.left.val : dfs(node.left);
    }
    // 递归搜索右子树
    // 如果当前右子树不是叶子节点就递归遍历右子树
    if (node.right != null && !isLeafNode(node.right)) {
        res += dfs(node.right);
    }
    return res;
}
// 判断节点是否是叶子节点
// 如果当前节点的左右子树都为空, 那么该节点就是叶子节点
public static boolean isLeafNode(TreeNode node) {
    return node.left == null && node.right == null;
}

广度优先搜索：

public int sumOfLeftLeaves(TreeNode root) {
    // 空树
    if (root == null) {
        return 0;
    }
    int res = 0;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int len = queue.size();
        while (len-- > 0) {
            TreeNode node = queue.poll();
            // 左子树不为空
            if (node.left != null) {
                // 左子树是叶子节点, 则累加节点值
                if (isLeafNode(node.left)) {
                    res += node.left.val;
                //     不是叶子节点, 将节点加入队列
                } else {
                    queue.offer(node.left);
                }
            }
            // 右子树不空
            if (node.right != null) {
                // 右子树不是叶子节点, 将节点加入队列
                if (!isLeafNode(node.right)) {
                    queue.offer(node.right);
                }
            }
        }
    }
    return res;
}