算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
今天和大家聊的问题叫做 左叶子之和,我们先来看题面:
https://leetcode-cn.com/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;
}
};
好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。