404. 左叶子之和
题目描述：给定二叉树的根节点 root ，返回所有左叶子之和。
解答：
法一：迭代法（层序遍历）
看到本题首先思考的是，如何确定是左叶子？叶子很好确定，左右子节点均为空即可，但是左叶子应该如何确定？
经过观察，如果将空节点也当作一个存在的节点，每一层的左节点在该层中序号数为2的倍数（0，2，4，8......）。
因此可以采用层序遍历，将空节点也入队，视为一个节点，但是不进行处理，仅用于计数。遇到左右子节点均为空且对2求余为0的节点（即为左叶子）求和即可。
代码实现：
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
queueque;
int sum = 0;
//只有一个节点的树额外处理
if (root->left == NULL && root->right == NULL) return sum;
que.push(root);
while(!que.empty()){
int size = que.size();
for (int i = 0; ileft == NULL && p->right == NULL && i%2 == 0)
sum += p->val;
que.push(p->left);
que.push(p->right);
}
}
}
return sum;
}
};
法二：递归实现
其实确定一个节点是左叶子主要得看他得父节点，单看他是看不出来的，必须要通过节点的父节点来判断其左孩子是不是左叶子
如果该节点的左节点不为空，该节点的左节点的左节点为空，该节点的左节点的右节点为空，则找到了一个左叶子，判断代码如下：
if (node->left != NULL && node->left->left == NULL && node->left->right == NULL) {
左叶子节点处理逻辑
}
依然还是考虑递归三部曲：
（1）参数和返回值： 判断一个树的左叶子节点之和，那么一定要传入树的根节点，递归函数的返回值为数值之和，所以为int
（2）终止条件：if（node == NULL）return 0；
（3）内部处理逻辑： 当遇到左叶子节点的时候，记录数值，然后通过递归求取左子树左叶子之和、右子树左叶子之和，相加便是整个树的左叶子之和。
代码实现：
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if(root == NULL) return 0;
int leftValue = sumOfLeftLeaves(root->left); // 左
int rightValue = sumOfLeftLeaves(root->right); // 右
// 中
int midValue = 0;
if (root->left && !root->left->left && !root->left->right)
midValue = root->left->val;
int sum = midValue + leftValue + rightValue;
return sum;
}
};
513. 找树左下角的值
题目描述：
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
解答：
法一：迭代法（层序遍历）
层序遍历解决这个属实简单，直接层序遍历至最底层，返回最底层的第一个值即可。
代码实现：
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
queueque;
que.push(root);
int num = 0;
while(!que.empty()){
int size = que.size();
for (int i = 0; ival;
que.pop();
if (p->left) que.push(p->left);
if (p->right) que.push(p->right);
}
}
return num;
}
};
法二：递归法
最底层的左下角节点，如何找到最底层？和二叉树的深度类似，先找最大深度，再找左边节点。
那么如何找最左边的呢？可以使用前序遍历，这样才先优先左边搜索，然后记录深度最大的叶子节点，此时就是树的最后一行最左边的值。
递归三要素：
（1）参数和返回值：根节点用于遍历，再用一个参数记录深度，无需返回值（关于是否需要返回值见下一篇博客：路径总和）
（2）终止条件：当遇到叶子节点的时候，更新一下最大的深度。
（3）内部处理逻辑：在找最大深度的时候，递归的过程中依然要使用回溯
代码实现：
class Solution {
public:
int maxLen = INT_MIN;
int maxleftValue;
void traversal(TreeNode* root, int leftLen) {
if (root->left == NULL && root->right == NULL) {
if (leftLen > maxLen) {
maxLen = leftLen;
maxleftValue = root->val;
}
return;
}
if (root->left) {
leftLen++;
traversal(root->left, leftLen);
leftLen--; // 回溯
}
if (root->right) {
leftLen++;
traversal(root->right, leftLen);
leftLen--; // 回溯
}
return;
}
int findBottomLeftValue(TreeNode* root) {
traversal(root, 0);
return maxleftValue;
}
};
