013.左叶子之和_云泊683的博客-爱代码爱编程
题目链接:力扣
大概思路:
左叶子的定义:
一个作父节点的左子树,是叶子节点。
思路:
后序遍历的基础上,加上判断左子树的逻辑,判断为左子树,返回值,然后左右子树的值相加。
递归三部曲:
1.确定递归函数的参数和返回值:
参数传入一个根节点,返回类型是int
int sumOfLeftLeaves(TreeNode* root)
2.明确终止条件:
遍历的过程中,节点等于空,返回
if (root == NULL) return 0;
3.设计单层递归逻辑:
后序遍历,然后在向左递归的代码下里添加”收集左叶子值的代码“,收集完左右子树的左叶子值,计算和,返回和,结束。
为啥在向左递归的代码下里'添加收集左叶子值'的代码?
因为向下递归的过程中,父节点的左子树才有可能有左叶子,而父节点的右子树不行
(这里的左右子树可能有歧义,例如左子树可能9-6-7(以3为父),也可能是6(以9为父),右子树同理)
这个解释描述的是这样一种情况,比如9-6-7,9为当前节点(父节点),然后左叶子只有父节点的左子树6有,右子树7没有。
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;
总代码:
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;
}
};
疑问:
求左右子树的左节点之和的代码是怎么让左节点他们的和相加的,感觉也没有加法啊??
哦哦,可能晚上头已经有点昏了,靠sum来加的,每一条最小分支最多只有一个左节点,然后左右子树(这里的规模是最小分支)都在父节点那相加,然后不断向上模拟这个行为,得到根节点的两左右子树的左节点值之和。
个人想法:
有很多时间在摸鱼,但不知道如何去处理。。算了,也处理不了。(也不一定)