NC248. 左叶子之和
描述
示例1
输入:
{1,2}
输出:
2
示例2
输入:
{1,2,3,4,5}
输出:
4
示例3
输入:
{1,2,3,4,5,6}
输出:
10
C++ 解法, 执行用时: 3ms, 内存消耗: 392KB, 提交时间: 2021-12-11
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
int sumOfLeftLeaves(TreeNode* root) {
// write code here
if(root==nullptr)
return 0;
TreeNode* p=root->left;
if(p&&p->left==nullptr&&p->right==nullptr)
return p->val+sumOfLeftLeaves(root->right);
else
return sumOfLeftLeaves(root->left)+sumOfLeftLeaves(root->right);
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 396KB, 提交时间: 2022-03-28
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
int leftTotalSum=0;
void traverseMiddle(TreeNode* cur,bool isLeft){
if(cur!=nullptr&&cur->left==nullptr&&cur->right==nullptr){
if(isLeft){
leftTotalSum=leftTotalSum+cur->val;
}
return;
}
else if(cur!=nullptr){
traverseMiddle(cur->left, true);
traverseMiddle(cur->right, false);
}
}
int sumOfLeftLeaves(TreeNode* root) {
// write code here
if(root==nullptr)
return 0;
traverseMiddle(root, true);
return leftTotalSum;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 396KB, 提交时间: 2022-02-08
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/*
方法一：广度优先搜索（BFS）
思路
每遍历到一个节点就检查一下它的左孩子是不是叶子节点，是就把它的值累加到结果中去
DFS也可以，随便一种遍历都行
复杂度分析
时间复杂度和空间复杂度都是O(n)。
*/
int sumOfLeftLeaves1(TreeNode* root) {
int sum = 0;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()) {
TreeNode* node = q.front(); q.pop();
if(node->left != NULL) {
if(node->left->left == NULL && node->left->right == NULL)
sum += node->left->val; // 这是个左叶子节点，累加上它的值
q.push(node->left);
}
if(node->right != NULL)
q.push(node->right);
}
return sum;
}
/*
方法二：DFS（递归实现）
*/
int sumOfLeftLeaves(TreeNode* root) {
dfs(root, true);
return sum;
}
private:
int sum = 0;
void dfs(TreeNode* root, bool flag) {
if(root == NULL) return;
if(root->left == NULL && root->right == NULL && flag)
sum = sum + root->val;
dfs(root->left, true);
dfs(root->right, false);
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 396KB, 提交时间: 2022-02-05
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
int sumOfLeftLeaves(TreeNode* root) {
// write code here
if(!root) return 0;
int sum_num=0;
if(root->left && !root->left->left && !root->left->right){
sum_num = root->left->val;
sum_num += sumOfLeftLeaves(root->right);
return sum_num;
}else{
sum_num += sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
return sum_num;
}
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 396KB, 提交时间: 2022-01-13
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
int sum=0;
int sumOfLeftLeaves(TreeNode* root) {
// write code here
dfs(root,true);
return sum;
}
void dfs(TreeNode* root, bool flag){
if(root == NULL){
return ;
}
if(root->left == NULL && root->right == NULL && flag){
sum = sum + root->val;
}
dfs(root->left,true);
dfs(root->right,false);
}
};