首页 > 试题广场 >

左叶子之和

[编程题]左叶子之和
  • 热度指数：2923 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
计算给定二叉树的左叶子之和。

树上叶子节点指没有后继节点的节点，左叶子指连向父节点的左侧的叶子节点。

样例 2 解释：

叶子节点有 4 ， 5 ，3，左叶子只有 4 ，所以答案返回 4

样例 3 解释

叶子节点有 4 ， 5 ，6，左叶子有 4 ， 6，所以答案返回 10

数据范围：树上节点的数量满足 ，节点上的值满足
示例1

输入

{1,2}

输出

2
示例2

输入

{1,2,3,4,5}

输出

4
示例3

输入

{1,2,3,4,5,6}

输出

10

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
C++
牛娃牛娃头像 牛娃牛娃 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int sumOfLeftLeaves(TreeNode* root) {
        // write code here
        if(root ==nullptr)return 0;
        int leftval =sumOfLeftLeaves(root->left);
        int rightval=sumOfLeftLeaves(root->right);
        int  midval=0;
        if(root->left&&!root->left->left&&!root->left->right){
            midval= root->left->val;
        }
        int sum =midval+leftval+rightval;
        return sum;

    }
};
发表于 2022-04-13 18:57:32 回复(0)
Java
菲尼克斯弗兰克头像 菲尼克斯弗兰克
dfs处理，辅助函数多传入一个flag就好，用于判断是不是左边的叶子 
public class Solution {
    public int sumOfLeftLeaves (TreeNode root) {
        dfs(root, true);
        return cnt;
    }
    public int cnt = 0;
    public void dfs(TreeNode root, boolean flag) {
        if (root == null) return;
        if (root.left == null && root.right == null && flag) {
            cnt += root.val;
        }
        dfs(root.left, true);
        dfs(root.right, false);
    }
}
发表于 2022-01-08 10:42:50 回复(0)
Java
pein531头像 pein531
用BFS（DFS也可以，随便一种遍历都行），每遍历到一个节点就检查一下它的左孩子是不是叶子节点，是就把它的值累加到结果中去。时间复杂度和空间复杂度都是O(n)。 
import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int sumOfLeftLeaves (TreeNode root) {
        // write code here
        int sum = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        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;      // 这是个左叶子节点，累加上它的值
                }
                queue.offer(node.left);
            }
            if(node.right != null){
                queue.offer(node.right);
            }
        }
        return sum;
    }
}

编辑于 2021-12-11 15:41:05 回复(0)
C
穗村看板娘头像 穗村看板娘
int sumOfLeftL 
int sumOfLeftLeaves(struct TreeNode* root ) 
{
    int leftsum = 0;
    if(root == NULL)
    {
        return 0;
    }

    if(root->left && root->left->left ==NULL&& root->left->right ==NULL)
    {
        leftsum = root->left->val;
    }
    leftsum += sumOfLeftLeaves(root->left);
    int rightsum = sumOfLeftLeaves(root->right);

    return leftsum +rightsum ;
    // write code here
}
发表于 2022-09-24 19:02:09 回复(0)
Rust
老刘001头像 老刘001 
/**
 * #[derive(PartialEq, Eq, Debug, Clone)]
 * pub struct TreeNode {
 *     pub val: i32,
 *     pub left: Option<Box<TreeNode>>,
 *     pub right: Option<Box<TreeNode>>,
 * }
 *
 * impl TreeNode {
 *     #[inline]
 *     fn new(val: i32) -> Self {
 *         TreeNode {
 *             val: val,
 *             left: None,
 *             right: None,
 *         }
 *     }
 * }
 */
struct Solution{

}

impl Solution {
    fn new() -> Self {
        Solution{}
    }

    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    *
    * 
        * @param root TreeNode类 
        * @return int整型
    */
    pub fn sumOfLeftLeaves(&self, root: Option<Box<TreeNode>>) -> i32 {
        // write code here
        if root.is_none() {0} else {
            self.left_leave_sum(&root.as_ref().unwrap().left, true) + 
            self.left_leave_sum(&root.as_ref().unwrap().right, false)
        }
    }

    fn left_leave_sum(&self, node: &Option<Box<TreeNode>>, from_left_edge: bool) -> i32 {
        if node.is_none() {return 0}
        if node.as_ref().unwrap().left.is_none() && node.as_ref().unwrap().right.is_none() && from_left_edge {
            node.as_ref().unwrap().val
        } else {
            self.left_leave_sum(&node.as_ref().unwrap().left, true) + 
            self.left_leave_sum(&node.as_ref().unwrap().right, false)
        }
    }
}

发表于 2023-08-31 22:03:26 回复(0)
Python3
danspace头像 danspace 
class Solution:
    def sumOfLeftLeaves(self , root: TreeNode) -> int:
        # write code here
        l = []
        def isLeaf(node):
            # 判断节点是否为叶子节点
            if node is not None and node.left is None and node.right is None:
                return True 
            return False

        def dfs(root):
            if not root:
                return 
            if isLeaf(root.left):
                l.append(root.left.val)
            dfs(root.left)
            dfs(root.right)
        dfs(root)
        return sum(l)

发表于 2023-04-27 14:19:09 回复(0)
小谷围做题家头像 小谷围做题家 
package main
// import "fmt"
import . "nc_tools"
/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return int整型
*/
func sumOfLeftLeaves( root *TreeNode ) int {
    if root==nil{
        return 0
    }
    if root.Left!=nil&&root.Left.Left==nil&&root.Left.Right==nil{
        return root.Left.Val+sumOfLeftLeaves(root.Right)
    }
    return sumOfLeftLeaves(root.Left)+sumOfLeftLeaves(root.Right)
}

发表于 2023-01-31 22:59:00 回复(0)
Java
牛客用户007头像 牛客用户007 
import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型
     */
    int res = 0;
    public int sumOfLeftLeaves (TreeNode root) {
        // write code here
        if (root == null) return 0;
        preOrder(root);
        return res;
    }

    private void preOrder(TreeNode t) {
        if (t != null) {
            if (t.left != null && t.left.left == null && t.left.right == null) {
                res = res + t.left.val;
            }
            preOrder(t.left);
            preOrder(t.right);
        }
    }
}

发表于 2022-09-13 12:56:27 回复(0)
Java
BlueProtocol头像 BlueProtocol 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型
     */
    public int sumOfLeftLeaves (TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left != null) {
            if (root.left.left == null && root.left.right == null) {
                // 叶子节点
                return root.left.val + sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);

            }
        }
        return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);

    }
}

发表于 2022-08-18 12:57:52 回复(0)
Java
Isolated_Island头像 Isolated_Island 
public class Solution {
    public int sumOfLeftLeaves (TreeNode root) {
        if (root == null) {
            return 0;
        }
        TreeNode left = root.left;
        if (left != null && left.left == null && left.right == null) {
            return left.val + this.sumOfLeftLeaves(root.right);
        }
        return this.sumOfLeftLeaves(root.left) + this.sumOfLeftLeaves(root.right);
    }
}

发表于 2022-05-05 14:39:59 回复(0)
Java
牛客280397572号头像 牛客280397572号 
import java.util.*;

public class Solution {
    public int sumOfLeftLeaves (TreeNode root) {
        if (root == null) { return 0; }
        if (isLeaf(root.left)) { //若节点左孩子为叶节点，返回其值并加上右子树中左叶子的值
            return root.left.val + sumOfLeftLeaves(root.right); 
        } else { //否则返回该节点左子树左叶子的值加上右子树左叶子的值
            return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
        }
    }
    
    private boolean isLeaf(TreeNode root) { //判断节点是否为叶节点
        if (root == null) { return false; }
        return root.left == null && root.right == null;
    }
}

发表于 2022-04-16 00:28:09 回复(0)
可吧幸头像 可吧幸
采用广度优先遍历的方法。 第一步:从根节点开始，先将根节点入队。 第二步:将队头节点出队，然后判断节点的左右指针是否为空，这里就有三种情况了，①左右指针都不为空，则将两个节点按序入队。②左指针为空，右指针不为空，则将右节点入队，*同时把节点的值递加给一个全局变量。③左指针不为空，右指针为空，则将左指针入队即可。 循环进行第二步，直到队列为空。
发表于 2022-01-19 10:17:25 回复(0)
提交观点

问题信息

树 dfs 广度优先搜索(BFS)
难度：
12条回答 2564浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号