算法力扣刷题记录 四十七【404.左叶子之和】

前言

二叉树篇，继续。
记录 四十七【404.左叶子之和】

---

一、题目阅读

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

示例 1：

输入: root = [3,9,20,null,null,15,7] 
输出: 24 
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

示例 2:

输入: root = [1]
输出: 0

提示:

节点数在 [1, 1000] 范围内
-1000 <= Node.val <= 1000

---

二、尝试实现

二叉树操作：递归和迭代。所以从两个方面尝试。

（1）递归思路

1. 确定一种遍历顺序。用前序和后序的多，中序比较少，所以经验考虑前序和后序。后序一般需要中间节点获取左右子树内容后向上返回信息，这里不太需要。所以确定前序（中左右）。
2. 确定递归参数：节点TreeNode* cur肯定有；要统计和sum，再来一个int& sum。如果遇到左叶子，sum + 数值。
3. 确定返回值：参数的sum已经记录和，所以返回值void。
4. 确定终止条件：当遇到叶子节点返回。右叶子不需要加，但是得回归，所以定在叶子节点，return。
5. 确定逻辑：

• cur传入的节点就是中，中节点不需要处理；
• 先看cur->left，如果左子树不是叶子节点，需要深入遍历：traversal（cur->left）；如果左子树是叶子节点，sum+数值，不需要深入遍历。
• 再对cur->right，不需要加右叶子，所以深入遍历。

代码实现【递归+前序】

/*** 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,int& sum){if(!cur->left && !cur->right) return;if(cur->left){if(!cur->left->left && !cur->left->right){sum += cur->left->val;}else{traversal(cur->left,sum);}}if(cur->right) traversal(cur->right,sum);return;}int sumOfLeftLeaves(TreeNode* root) {int sum = 0;traversal(root,sum);return sum;}
};

（2）迭代思路

1. 延续递归遍历顺序：中左右。所以基于前序的迭代实现，需要一个stack；
2. 放入右节点时，直接入栈；
3. 放入左节点时：如果是叶子，sum求和，不入栈；不是叶子，再入栈。

代码实现【迭代】

/*** 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) {int sum = 0;stack<TreeNode*> st;if(!root->left &&!root->right) return 0;st.push(root);while(!st.empty()){TreeNode* cur = st.top();st.pop();if(cur->right) st.push(cur->right);if(cur->left){if(!cur->left->left && !cur->left->right){//叶子节点sum += cur->left->val;}else{st.push(cur->left);}}}return sum;}
};

---

三、参考学习

参考学习链接

学习内容

1. 概念确定：左叶子——先是叶子节点，再该节点是其父节点的左孩子；
2. 思路：如何搜集节点？如果处理节点是当前判断节点，只能判断该节点是叶子结点吗？不能确定它是父节点的左孩子。所以，必须在父节点处判断左孩子是不是要搜集的节点。（和尝试实现中的思路一致。）
3. 遍历顺序：后序。（不同之处）原因：他认为先搜集左子树中的左叶子之和，再搜集右子树中的左叶子之和，回到中间后，把两边左叶子之和相加。类似深度处理。
4. 后序逻辑：

• 递归的参数：节点TreeNode* cur，传入当前节点；
• 递归的返回值：子树的左叶子之和，int类型；
• 递归的终止条件：
  • cur空，return 0 ；子树没有。
  • cur是叶子节点，return 0；叶子节点的左叶子没有。
  • 其实，如果控制遍历时if(cur->left)存在，那么cur不用判断是否为空。
• 逻辑：
  • 获取左边的左叶子：当左边return 0 回到上一层，在父节点处判断左孩子存在且左孩子是叶子，搜集数值；
  • 获取右边的左叶子；traversal（cur->right）。
  • 最后给上一层返回左边+右边。

代码实现【后序+递归】

/*** 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) {if(!root) return 0;if(!root->left && !root->right) return 0;int leftnum = sumOfLeftLeaves(root->left);if(root->left && !root->left->left && !root->left->right){ //搜集数值leftnum = root->left->val;}int rightnum = sumOfLeftLeaves(root->right);return leftnum+rightnum;}
};

---

总结

【404.左叶子之和】：

（欢迎指正，转载标明出处）