大家好呀，我是帅蛋。
今天解决左叶子之和，一个理解对了左叶子概念就能理论 AC 的题，同样也可以反过来看，理解错了，WA 与你相随。
话不多说，我们搞起这道标号 404 ~
LeetCode 404：左叶子之和
题意
给定二叉树的根节点 root，返回所有左叶子之和。
示例
输入：root = [3,9,20,null,null,15,7]
输出：24
解释：在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24。
提示
- 节点数在 [1,1000] 范围内
- -1000 <= Node.val <= 1000
题目解析
难度简单，只要明白了什么是左叶子节点，这道题就理论上解决了。
叶子节点是没有孩子节点的节点，那左叶子节点就是“是左孩子且该左孩子没有孩子节点”。
像下图，它的左叶子之和是 2。
再比如下面这张图，它的左叶子之和呢？
答案是 0，因为它没有左叶子节点。你肯定也答对了叭~
至于具体的解法，其实就是遍历整棵树：
- 如果遍历的当前节点的左孩子是一个叶子节点，则左孩子的值累加入结果。
- 如果遍历的当前节点的左孩子不是叶子节点，则继续遍历。
递归法
在既然要遍历二叉树，我们都知道二叉树有前中后序遍历及层次遍历，但是这里不推荐层次遍历。
因为篇幅原因，我这里以前序遍历为例，解决本题。不熟悉二叉树遍历（递归）的可以看下面这篇文章：
根据【递归算法】文章中讲的，实现递归，需要两步：
- 找出重复的子问题（递推公式）。
- 终止条件。
根据上面讲的实现递归的两步来实现：
(1) 找出重复的子问题。
这个很好找，前序遍历的顺序是：根、左子树、右子树。
对应到本题是：左叶子节点操作，递归左子树，递归右子树。
对于左子树或者右子树来说，也是同样的操作顺序。
所以这个重复的子问题就出来了，先判断当前节点的左孩子是否为左叶子节点，再遍历左子树，最后遍历右子树。
# 如果遍历到当前节点的左孩子为左叶节点，则将左孩子的值加入 res if root.left != None and root.left.left == None and root.left.right == None: self.res += root.left.val # 遍历左子树 self.sumOfLeftLeaves(root.left) # 遍历右子树 self.sumOfLeftLeaves(root.right)
(2) 确定终止条件。
对于二叉树的遍历来说，想终止，即没东西遍历了，没东西遍历自然就停下来了。
# 递归中止条件 if root == None: return 0
这两点确定好了，代码也就出来了。
Python 代码实现
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: # 初始化 res def __init__(self): self.res = 0 def sumOfLeftLeaves(self, root: TreeNode) -> int: # 递归中止条件 if root == None: return 0 # 如果遍历到当前节点的左孩子为左叶节点，则将左孩子的值加入 res if root.left != None and root.left.left == None and root.left.right == None: self.res += root.left.val # 遍历左子树 self.sumOfLeftLeaves(root.left) # 遍历右子树 self.sumOfLeftLeaves(root.right) return self.res
Java 代码实现
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { int res = 0; public int sumOfLeftLeaves(TreeNode root) { // 递归中止条件 if(root == null){ return 0; } // 如果遍历到当前节点的左孩子为左叶节点，则将左孩子的值加入 res if(root.left != null && root.left.left == null && root.left.right == null){ res += root.left.val; } // 遍历左子树 sumOfLeftLeaves(root.left); // 遍历右子树 sumOfLeftLeaves(root.right); return res; } }
本题解，每个节点都会被访问到，所以时间复杂度为 O(n)。
此外在递归过程中调用了额外的栈空间，栈的大小取决于二叉树的高度，二叉树最坏情况下的高度为 n，所以空间复杂度为 O(n)。
非递归法（迭代）
非递归的做法，又叫迭代法。迭代法就是不断地将旧的变量值，递推计算新的变量值。
迭代法是用栈来做，对二叉树前序遍历迭代法不太了解的蛋粉可以看下面这篇文章：
既然递归法用的是前序遍历，那迭代法我也用前序遍历来讲解。
根据栈“先入后出”的特点，结合前序遍历的顺序，迭代的过程其实很好理解：
每次都是先将根节点放入栈，然后右子树，最后左子树。
具体步骤如下所示：
- 初始化维护一个栈，将根节点入栈。
- 当栈不为空时，弹出栈顶元素 node：
- 如果 node 的左孩子为叶子节点，该左孩子数值加入结果 res。
- 如果 node 有右子树，则右子树入栈。
- 如果 node 有左子树，则左子树入栈。
以下图为例：
首先初始化栈 stack 和结果 res。
# 初始化栈和结果 stack = [root] res = 0
栈不为空，栈顶元素出栈 node = 3，它的左孩子为 9 且左孩子为叶子节点，将左孩子的值累加 res。
# 弹出栈顶元素 node = stack.pop() # 如果当前节点的左孩子为左叶节点 if node.left != None and node.left.left == None and node.left.right == None: res += node.left.val
接下来是 node 的右孩子入栈，左孩子入栈。
# 右子树入栈 if node.right: stack.append(node.right) # 左子树入栈 if node.left: stack.append(node.left)
当栈不为空时，接下来的操作都是在重复上述的内容。
当栈为空时，结束，此时的 res = 24，即此二叉树的左叶子之和为 24。
Python 代码实现
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def sumOfLeftLeaves(self, root: TreeNode) -> int: # 空树，直接返回 0 if root == None: return 0 # 初始化栈和结果 stack = [root] res = 0 # 当栈不为空 while stack: # 弹出栈顶元素 node = stack.pop() # 如果当前节点的左孩子为左叶节点 if node.left != None and node.left.left == None and node.left.right == None: res += node.left.val # 右子树入栈 if node.right: stack.append(node.right) # 左子树入栈 if node.left: stack.append(node.left) return res
Java 代码实现
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public int sumOfLeftLeaves(TreeNode root) { // 空树，直接返回 0 if(root == null){ return 0; } // 初始化栈和结果 Stack<TreeNode> stack = new Stack<> (); stack.add(root); int res = 0; // 当栈不为空 while (!stack.isEmpty()) { // 弹出栈顶元素 TreeNode node = stack.pop(); // 如果当前节点的左孩子为左叶节点 if (node.left != null && node.left.left == null && node.left.right == null) { res += node.left.val; } // 右子树入栈 if (node.right != null){ stack.add(node.right); } // 左子树入栈 if (node.left != null){ stack.add(node.left); } } return res; } }
同样迭代法，时间复杂度为 O(n)，空间复杂度为 O(n)。
图解左叶子之和到这就结束辣，没骗你们叭？左叶子节点懂了，一切就很顺畅了。
用二叉树的遍历去解题，是二叉树中很容易碰到的方法，大家还得多总结多思考。
今天就到这了，记得帮我点赞 + 在看 + 转发一条龙呀，爱你们~
我是帅蛋，我们下次见！
