【原】LeetCode刷题实战404：左叶子之和

程序IT圈 2021-10-09

展开全文

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 左叶子之和，我们先来看题面：

https:///problems/sum-of-left-leaves/

Given the root of a binary tree, return the sum of all left leaves.

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

示例

3
   / \
  9 20
    / \
   15 7

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

解题

主要思路：

（1）直观的想，就是使用先序遍历，只不过是在递归的过程中，标识出当前结点是否是左子树，只有是左子树，且是叶子结点的时候，才进行数值统计；

class Solution {
public:

    void helper(TreeNode* root,int& sum,bool is_left){
        if(root==NULL){//空节点返回
            return;
        }
        //为叶子结点
        if(root->left==NULL&&root->right==NULL){
            if(is_left){//为左结点
                sum+=root->val;
            }
            return;
        }
        helper(root->left,sum,true);//遍历左子树，标识是左子树
        helper(root->right,sum,false);//遍历右子树，标识不是左子树
    }

    int sumOfLeftLeaves(TreeNode* root) {
      //处理特殊的情形
        if(root==NULL||(root->left==NULL&&root->right==NULL)){
            return 0;
        }
        int sum=0;
        helper(root,sum,true);
        return sum;
    }
};