據(jù)說(shuō)是Facebook的新題嘹屯，然而被LeetCode標(biāo)為easy攻询。
鏈接：Sum of Left Leaves
題目就是讓找一棵樹(shù)左葉子的總和。
想一想州弟，不到一分鐘就有了思路钧栖，果然是easy題……
第一版本：
需要判斷當(dāng)前走到的節(jié)點(diǎn)是不是為左葉子低零。就這一個(gè)問(wèn)題。
這還不好辦拯杠，來(lái)個(gè)flag標(biāo)記一下掏婶，于是有了第一個(gè)AC的版本
public class Solution {
public int sumOfLeftLeaves(TreeNode root) {
return helper(root, false);
}
private int helper(TreeNode node, boolean isLeft) {
if (node == null) {
return 0;
}
if (node.left == null && node.right == null && isLeft) {
return node.val;
}
return helper(node.left, true) + helper(node.right, false);
}
}
結(jié)果還不錯(cuò)，但是想了想潭陪，能不能把傳的boolean類型去掉雄妥。
于是有了第二個(gè)AC的版本。
第二版本：
public class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if (root == null) {
return 0;
}
int sum = 0;
if (root.left != null && root.left.left == null && root.left.right == null) {
sum += root.left.val;
} else {
sum += sumOfLeftLeaves(root.left);
}
sum += sumOfLeftLeaves(root.right);
return sum;
}
}
兩個(gè)版本都是用的遞歸依溯，根據(jù)LeetCode的runtime分析老厌，第一個(gè)版本要稍微快一點(diǎn)。
