一、题目描述

计算给定二叉树的所有左叶子之和。

示例:

    3
   / \
  9  20
    /  \
   15   7

在这个二叉树中,有两个左叶子,分别是 9 和 15,所以返回 24

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 左叶子之和( LeetCode 404 ): https://leetcode-cn.com/problems/sum-of-left-leaves
class Solution {
    public int sumOfLeftLeaves(TreeNode root) {

        // 这道题目考察的就是左叶子节点的定义
        // 左叶子节点具备以下几个特征
        // 1、该节点 node 具备父节点 root
        // 2、该节点 node 是父节点的左子节点,即 node = root.left
        // 3、该节点 node 的左子节点为空,即 node.left = null
        // 4、该节点 node 的右子节点为空,即 node.right = null

        // 利用这几个特征来找出所有的左叶子节点
        return sumOfLeftLeaves(root, false);
    }

    // isLeftNode 表明 node 是否是它的父节点的左子节点
    public int sumOfLeftLeaves(TreeNode node, boolean isLeftNode){

        // 边界情况处理
        if(node == null){
            return 0;
        }

        // 左叶子节点具备以下几个特征
        // 1、该节点 node 具备父节点 root
        // 2、该节点 node 是父节点的左子节点,即 node = root.left
        // 3、该节点 node 的左子节点为空,即 node.left = null
        // 4、该节点 node 的右子节点为空,即 node.right = null

        // isLeftNode 表明 node 是否是它的父节点的左子节点
        // 满足这三个判断的话,把这个节点值加入到结果中
        if(isLeftNode && node.left == null && node.right == null){
            // 把这个左叶子节点的值返回记录
            return node.val;
        }

        // 继续去搜索 node 的左叶子节点,node.left 肯定是 node 的左子节点
        // 所以,对于 node.left 来说,isLeftNode 为 true
        // 也就是说,node.left 这个节点值有可能加入到计算中,但还取决于它是否是叶子节点
        int leftSum = sumOfLeftLeaves(node.left, true);

        // 继续去搜索 node 的右叶子节点,node.right 肯定不是 node 的左子节点
        // 所以,对于 node.right 来说,isLeftNode 为 false
        // 也就是说,node.right 这个节点值是肯定不能加入到计算中的
        int rightSum = sumOfLeftLeaves(node.right, false);

        // 这样,就能计算所有的左叶子节点之和
        return leftSum + rightSum;
    }
}

2、C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 左叶子之和( LeetCode 404 ): https://leetcode-cn.com/problems/sum-of-left-leaves
class Solution
{
public:
    int sumOfLeftLeaves(TreeNode* root)
    {

        // 这道题目考察的就是左叶子节点的定义
        // 左叶子节点具备以下几个特征
        // 1、该节点 node 具备父节点 root
        // 2、该节点 node 是父节点的左子节点,即 node = Troot->left
        // 3、该节点 node 的左子节点为空,即 node->left = NULL
        // 4、该节点 node 的右子节点为空,即 node->right = NULL

        // 利用这几个特征来找出所有的左叶子节点
        return sumOfLeftLeaves(root, false);
    }

    // isLeftNode 表明 node 是否是它的父节点的左子节点
    int sumOfLeftLeaves(TreeNode* node, bool isLeftNode)
    {

        // 边界情况处理
        if (node == NULL)
        {
            return 0;
        }

        // 左叶子节点具备以下几个特征
        // 1、该节点 node 具备父节点 root
        // 2、该节点 node 是父节点的左子节点,即 node = root->left
        // 3、该节点 node 的左子节点为空,即 node->left = NULL
        // 4、该节点 node 的右子节点为空,即 node->right = NULL

        // isLeftNode 表明 node 是否是它的父节点的左子节点
        // 满足这三个判断的话,把这个节点值加入到结果中
        if (isLeftNode && node->left == NULL && node->right == NULL)
        {
            // 把这个左叶子节点的值返回记录
            return node->val;
        }

        // 继续去搜索 node 的左叶子节点,node->left 肯定是 node 的左子节点
        // 所以,对于 node->left 来说,isLeftNode 为 true
        // 也就是说,node->left 这个节点值有可能加入到计算中,但还取决于它是否是叶子节点
        int leftSum = sumOfLeftLeaves(node->left, true);

        // 继续去搜索 node 的右叶子节点,node->right 肯定不是 node 的左子节点
        // 所以,对于 node->right 来说,isLeftNode 为 false
        // 也就是说,node->right 这个节点值是肯定不能加入到计算中的
        int rightSum = sumOfLeftLeaves(node->right, false);

        // 这样,就能计算所有的左叶子节点之和
        return leftSum + rightSum;
    }
};

3、Python 代码

# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者:程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 左叶子之和( LeetCode 404 ): https://leetcode-cn.com/problems/sum-of-left-leaves
class Solution:
    def sumOfLeftLeaves(self, root: TreeNode) -> int:

        # 这道题目考察的就是左叶子节点的定义
        # 左叶子节点具备以下几个特征
        # 1、该节点 node 具备父节点 root
        # 2、该节点 node 是父节点的左子节点,即 node = root.left
        # 3、该节点 node 的左子节点为空,即 node.left = null
        # 4、该节点 node 的右子节点为空,即 node.right = null

        # 利用这几个特征来找出所有的左叶子节点
        return self.sumOfLeftLeavessub(root, False)

    # isLeftNode 表明 node 是否是它的父节点的左子节点
    def sumOfLeftLeavessub(self, node: TreeNode,isLeftNode:bool) -> int:
        # 边界情况处理
        if not node :
            return 0


        # 左叶子节点具备以下几个特征
        # 1、该节点 node 具备父节点 root
        # 2、该节点 node 是父节点的左子节点,即 node = root.left
        # 3、该节点 node 的左子节点为空,即 node.left = null
        # 4、该节点 node 的右子节点为空,即 node.right = null

        # isLeftNode 表明 node 是否是它的父节点的左子节点
        # 满足这三个判断的话,把这个节点值加入到结果中
        if isLeftNode and  not node.left and not node.right :
            # 把这个左叶子节点的值返回记录
            return node.val


        # 继续去搜索 node 的左叶子节点,node.left 肯定是 node 的左子节点
        # 所以,对于 node.left 来说,isLeftNode 为 true
        # 也就是说,node.left 这个节点值有可能加入到计算中,但还取决于它是否是叶子节点
        leftSum = self.sumOfLeftLeavessub(node.left, True)

        # 继续去搜索 node 的右叶子节点,node.right 肯定不是 node 的左子节点
        # 所以,对于 node.right 来说,isLeftNode 为 false
        # 也就是说,node.right 这个节点值是肯定不能加入到计算中的
        rightSum = self.sumOfLeftLeavessub(node.right, False)

        # 这样,就能计算所有的左叶子节点之和
        return leftSum + rightSum

四、动画理解(没有声音)

发表评论

邮箱地址不会被公开。 必填项已用*标注