本文转载自微信公众号《代码随想录》，作者程序员卡尔。转载本文请联系CodeCaprice公众号。左叶子之和题目地址：https://leetcode-cn.com/problems/sum-of-left-leaves/计算给定二叉树的所有左叶子之和。例子：首先要注意判断的是左叶子，而不是二叉树的左节点，所以先别想着层序遍历。因为题目没有明确什么是左叶，所以我给左叶一个明确的定义：如果左节点不为空，且左节点没有左右孩子，那么这个节点就是左叶。想一想如下图在二叉树中，左边叶子的总和是多少？实际上是0，因为这棵树根本就没有左边的叶子！那么就无法判断当前节点是否是左叶子。需要判断它的左孩子是否通过该节点的父节点。不是左叶。如果该节点的左节点不为空，该节点的左节点的左节点为空，该节点的左节点的右节点为空，则找到一个左叶子，判断代码为如下：if(node->left!=NULL&&node->left->left==NULL&&node->left->right==NULL){左叶节点处理逻辑}递归方式递归的遍历顺序为后序遍历（左和右），因为需要通过递归函数对返回值进行累加求左叶值之和。.递归三部曲：1.确定递归函数的参数和返回值。判断一棵树的左叶节点之和，必须传入树的根节点，递归函数的返回值是值之和，所以用题为int中给出的函数即可。2.判断终止条件还是if(root==NULL)return0;3.判断单级递归的逻辑遇到左叶子结点，记录下值，然后通过递归计算左子树左叶子的和，而右子树左叶子的和为整棵树的左边叶子的总和。代码如下：intleftValue=sumOfLeftLeaves(root->left);//左intrightValue=sumOfLeftLeaves(root->right);//右//中intmidValue=0;if(root->left&&!root->left->left&&!root->left->right){midValue=root->left->val;}intsum=midValue+leftValue+rightValue;returnsum;整体发送代码如下：classSolution{public:intsumOfLeftLeaves(TreeNode*root){if(root==NULL)return0;intleftValue=sumOfLeftLeaves(root->left);//左intrightValue=sumOfLeftLeaves(root->right);//右//中intmidValue=0;if(root->left&&!root->left->left&&!root->left->right){//中midValue=root->left->val;}intsum=midValue+leftValue+rightValue;returnsum;}};以上代码精简之后如下：classSolution{public:intsumOfLeftLeaves(TreeNode*root){if(root==NULL)return0;intmidValue=0;if(root->left!=NULL&&root->left->left==NULL&&root->left->right==NULL){midValue=root->left->val;}returnmidValue+sumOfLeftLeaves(root->left)+sumOfLeftLeaves(root->rigHT）;}};迭代法这道题的迭代法可以用前中后序，只要算出左叶节点即可，然后参考文章二叉树：听说递归可以做，栈也可以做它！如BinaryTree:IterativeMethod的UnifiedWritingMethod，可以写出一个判断条件相同的前序遍历迭代方法。代码如下：classSolution{public:intsumOfLeftLeaves(TreeNode*root){stackst;if(root==NULL)return0;st.push(root);intresult=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);}returnresult;}};总结一下，这道题需要左叶求和，其实还是挺绕的，因为无法判断该节点是不是左叶节点。这时候就需要通过该节点的父节点来判断该节点的左孩子是否为左叶子。通常我们在解决二叉树问题的时候，习惯通过节点的左右孩子来判断节点的属性，但是在这个问题中我们需要通过节点的父节点来判断节点的属性.希望通过这个话题，可以拓展你对二叉树求解的思路。其他语言版本Java递归classSolution{publicintsumOfLeftLeaves(TreeNoderoot){if(root==null)return0;intleftValue=sumOfLeftLeaves(root.left);//左intrightValue=sumOfLeftLeaves(root.right);//右intmidValue=0;if(root.left!=null&&root.left.left==null&&root.left.right==null){//中midValue=root.left.val;}intsum=midValue+leftValue+rightValue;returnsum;}}代classSolution{publicintsumOfLeftLeaves(TreeNoderoot){if(root==null)return0;Stackstack=newStack<>();stack.add(root);intresult=0;while(!stack.isEmpty()){TreeNodenode=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);}returnresult;}}Python递归classSolution:defsumOfLeftLeaves(self,root:TreeNode)->int:ifnotroot:return0left_left_leaves_sum=self.sumOfLeftLeaves(root.left)#左right_left_leaves_sum=self.sumOfLeftLeaves(root.right)#右cur_left_leaf_val=0ifroot.leftandnotroot.left.leftandnotroot.left.right:cur_left_leaf_val=root.left.val#中returncur_left_leaf_val+left_left_leaves_sum+right_left_leaves_sum改代classSolution:defsumOfLeftLeaves(self,root:TreeNode)->int:"""Idea:Eachtimecheckcurrentnode'sleftnode.Ifcurrentnodedon'thaveone,skipit."""stack=[]ifroot:stack.append(root)res=0whilestack:#每次都把当前节点的左节点加进去.cur_node=stack.pop()ifcur_node.leftandnotcur_node.left.leftandnotcur_node.left.right:res+=cur_node.left.valifcur_node.left:stack.append(cur_node.left)ifcur_node.right:stack.append(cur_node.right)returnres
