【二叉树算法题记录】404. 左叶子之和

题目描述

给定二叉树的根节点 root ，返回所有左叶子之和。

题目分析

其实这题无论是迭代法还是递归法，最重要的是要明确判断左叶子的条件：当前节点有左孩子，且这个左孩子没有它的左孩子和右孩子。

迭代法

感觉只要二叉树相关的题递归想不出来，直接暴力上层序遍历就能解出来。迭代法真没什么难度，就是把内层while循环中处理当前节点的条件换成上面的逻辑就行，也即：

if(node->left && node->left->left==NULL && node->left->right == NULL) sum += node->left->val;

整体cpp代码：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {// 迭代法（层序遍历）queue<TreeNode*> q;int sum = 0;if(root!=NULL) q.push(root);while(!q.empty()){int size = q.size();while(size--){TreeNode* node = q.front();q.pop();if(node->left && node->left->left==NULL && node->left->right == NULL) sum += node->left->val;if(node->left) q.push(node->left);if(node->right) q.push(node->right);}}return sum;}
};

递归法

这里我和代码随想录中处理的不太一样，但是思路是一样的。我这里用了传出参数vector<int>& sum，所以我用什么遍历顺序都是对的。但是代码随想录中是用了int返回值，所以是要从下层传结果送至上层汇聚，那么这就必须要用后序遍历（左右中）。

我的cpp整体递归代码

注意：这里中左右的顺序可以任意变换，已经试过了，都能AC。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:void traversal(TreeNode* cur, vector<int>& sum){// 递归终止条件if(cur == NULL) return;if(cur->left) traversal(cur->left, sum);if(cur->right) traversal(cur->right, sum);// 单层递归逻辑：当该节点只有一个左孩子（左叶子）if(cur->left!=NULL && cur->left->left==NULL && cur->left->right==NULL){sum.push_back(cur->left->val);}}int sumOfLeftLeaves(TreeNode* root) {// 递归法vector<int> sum;traversal(root, sum);return accumulate(sum.begin(), sum.end(), 0);}
};

代码随想录的cpp整体递归代码

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;}
};