【刷题日记】二叉树-左叶子之和-L404-Easy
给定二叉树的根节点 root ，返回所有左叶子之和。
思路
- 思路 1
- 用一个标记来标识当前节点是否为左子节点（通过上一个父节点传递标记参数）。如果为左子节点且已经没有了左右子节点，则该左子节点为左叶子节点。
- 思路 2
- 不使用标记。通过父节点来判断父节点的左子节点是否为叶子节点。
代码
思路 1：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
void cal_left_leaves(TreeNode *root, int &res, bool is_left)
{
if (!root)
return;
cal_left_leaves(root->left, res, true);
cal_left_leaves(root->right, res, false);
if (!root->left && !root->right && is_left)
res += root->val;
}
int sumOfLeftLeaves(TreeNode* root) {
int res = 0;
cal_left_leaves(root, res, false);
return res;
}
};
|
思路 2：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if (root == NULL) return 0;
if (root->left == NULL && root->right== NULL) return 0;
int leftValue = sumOfLeftLeaves(root->left);
if (root->left && !root->left->left && !root->left->right) {
leftValue = root->left->val;
}
int rightValue = sumOfLeftLeaves(root->right);
int sum = leftValue + rightValue;
return sum;
}
};
|
