(第31天)【leetcode题解】404、左叶子之和

404、左叶子之和

题目描述

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

思路

1. 题目分析：

• 判断左叶子节点：A节点的左孩子不为空，且左孩子的左右孩子都为空，那么这个左孩子节点就是左叶子节点。

2.递归法：

• 递归函数的功能：返回以root为根节点的树的左叶子节点值之和。
• 参数和返回值：root表示(树或子树)根节点、返回int左叶子节点之和
• 终止条件：如果root为空，则以其为根节点的树的左叶子节点一定为空，返回0。
• 递归逻辑：后序遍历。因为要通过函数返回值来累加左叶子节点值。

3.迭代法：

• 在遍历过程中识别左叶子节点，并把左叶子节点的值累加。
• 任意一种遍历方式都可。

代码

递归法：

class Solution {
public://返回以root为根节点的树的左叶子节点值之和int sumOfLeftLeaves(TreeNode* root) {if (root == nullptr) return 0;//root为空，则该树的叶子节点也为空int leftValue = sumOfLeftLeaves(root->left); // 左子树所有左叶子节点值之和if (root->left != nullptr && root->left->left == nullptr && root->left->right == nullptr) {//判断root->left是否是左叶子leftValue = root->left->val;//得到左叶子的值}int rightValue = sumOfLeftLeaves(root->right); //右子树的所有左叶子节点值之和int sum = leftValue + rightValue; // 得到以当前root节点为根节点的树的左叶子节点值之和return sum;}
};

迭代法：

class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {stack<TreeNode*> st;if (root != nullptr) st.push(root);int result = 0;while (!st.empty()) {TreeNode* node = st.top(); st.pop();if (node->left != NULL && node->left->left == NULL && node->left->right == NULL) {result += node->left->val;  }if (node->right) st.push(node->right);if (node->left) st.push(node->left);}return result;}
};