LeetCode404. 左叶子之和
计算给定二叉树的所有左叶子之和。
思路：
首先由于计算左叶子之和，所以遍历的顺序一定是左在前，选用左右中的后续遍历进行递归比较合适。
由于判断是左叶子，不是左子树，所以层序遍历不可以用。
左叶子节点如何用代码定义？也就是当前节点的终止条件，节点A的左孩子不为空，且左孩子的左右孩子都为空的节点，为左叶子节点。
if (node->left != NULL && node->left->left == NULL && node->left->right == NULL) {
左叶子节点处理逻辑
}
如果遍历到空节点，那么左叶子值一定是0
1.确定参数和返回值。参数是当前节点，返回值是数值之和。
2.终止条件：遍历到空节点，左叶子一定为）
由于只可以通过父节点来判断是否是左叶子节点，所以当前节点为空和当前节点的左右孩子为空的情况都不在考虑范围之内，直接返回0即可
3.单层递归逻辑：
当遇到左叶子节点的时候，记录数值，然后通过递归求取左子树左叶子之和，和 右子树左叶子之和，相加便是整个树的左叶子之和。
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;
int leftValue = sumOfLeftLeaves(root.left); // 左
int rightValue = sumOfLeftLeaves(root.right); // 右
int midValue = 0;
if (root.left != null && root.left.left == null && root.left.right == null) {
midValue = root.left.val;
}
int sum = midValue + leftValue + rightValue; // 中
return sum;
}
}
迭代写法：
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if (root == null) return 0;
Stack<TreeNode> stack = new Stack<> ();
stack.add(root);
int result = 0;
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node.left != null && node.left.left == null && node.left.right == null) {
result += node.left.val;
}
if (node.right != null) stack.add(node.right);
if (node.left != null) stack.add(node.left);
}
return result;
}
}
层序遍历写法：
// 层序遍历迭代法
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
int sum = 0;
if (root == null) return 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
while (size -- > 0) {
TreeNode node = queue.poll();
if (node.left != null) { // 左节点不为空
queue.offer(node.left);
if (node.left.left == null && node.left.right == null){ // 左叶子节点
sum += node.left.val;
}
}
if (node.right != null) queue.offer(node.right);
}
}
return sum;
}
}