Leetcode：404.左叶子之和（C++）-创新互联

目录

问题描述：

实现代码与解析：

递归（后序）：

原理思路：

迭代（先序）：

原理思路：

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

示例 1：

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

示例 2:

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

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) 
    {
        if (root == NULL) return 0;
        int left=0;
        if (root->left && !root->left->left && !root->left->right) 
        { 
            left= root->left->val;
        }
        int leftValue = sumOfLeftLeaves(root->left);            
        int rightValue = sumOfLeftLeaves(root->right);  
        int sum = left+leftValue + rightValue;      
        return sum;
    }
};

也可以这样写：

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) 
    {
        if(root==NULL) return 0;
        int leftValue=sumOfLeftLeaves(root->left);
        if(root->left&&root->left->left==NULL&&root->left->right==NULL) left=root->left->val;//记录左叶子结点的值
        int rightValue=sumOfLeftLeaves(root->right);
        return leftValue+rightValue;
    }
};

其实就是把判断左子树为左叶子结点的步骤放在了中序上了而已，因为在中序判断左子树为左叶子结点的话，说明从左子树返回的值一定为0，那么我们直接在父结点给leftValue赋值即可，减少了一个变量而已，没什么区别。返回上一层的操作都还是在后序位置上。

精简版：

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) 
    {
        if(root==NULL) return 0;
        int left=0;
        if(root->left&&root->left->left==NULL&&root->left->right==NULL) left=root->left->val;
        return left+sumOfLeftLeaves(root->left)+sumOfLeftLeaves(root->right);
    }
};

  我们先要明白左叶子结点是什么？并不是左侧的结点，而是作为左孩子的叶子结点，如下图：

  因为我们要搜集的是左叶子结点，在遍历到所指向结点时，只能判断该结点是否为叶子结点，而不能判断是左叶子结点还是右叶子结点，所以我们要在父结点的时候就开始判断左子树是否为左叶子结点，大家可以跟着代码模拟着走一遍，题不难，但是有点绕。

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) 
    {
        int result=0;
        if(root==NULL) return result;
        stackst;
        st.push(root);
        while(!st.empty())
        {
            TreeNode* temp=st.top();
            st.pop();
            if(temp->left&&temp->left->left==NULL&&temp->left->right==NULL)
            {
                result+=temp->left->val;
            }
            if(temp->left) st.push(temp->left);
            if(temp->right) st.push(temp->right);
        }
        return result;
    }
};

用迭代法还是比较简单的，就是在原有的遍历代码（前中后序都可）上添加一下判断是否为左叶子结点的代码而已：

if(temp->left&&temp->left->left==NULL&&temp->left->right==NULL)
{
    result+=temp->left->val;
}

比较简单和容易理解，就不详细解析了。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧