手撸二叉树之左叶子之和

题目

计算给定二叉树的所有左叶子之和。

示例：

  3
   / \
  9  20
    /  \
   15   7

在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

解题思路

根据题意，我们可以利用深度优先搜索去遍历整个二叉树，去找到所有的左叶子节点，具体思路如下：

1. 定义一个全局变量用于记录左叶子节点的和；
2. 遍历二叉树，如果当前节点的左孩子和右孩子都为 null,并且当前的节点是左子树的节点，则判断这个是一个左叶子节点；反之，则继续遍历该节点的左孩子和右孩子，直到找出左叶子节点；
3. 如果当前节点是右子树的节点，并且不为null，则继续遍历该节点的左孩子，右孩子，直到找出左叶子节点；

代码实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    int ans = 0;
    public int sumOfLeftLeaves(TreeNode root) {
        addLeftLeaves(root);
        return ans;
    }
    public void addLeftLeaves(TreeNode root){
        if(root!=null){
            TreeNode l=root.left;
            TreeNode r=root.right;
            if(l!=null&&l.left==null&&l.right==null){
                ans+=l.val;
            }
            else{
                addLeftLeaves(l);
            }
            if(r!=null){
                addLeftLeaves(r);
            }
        }
    }
}

最后

复杂度分析：

• 时间复杂度：O(n)，其中 n 是树中的节点个数。

• 空间复杂度：O(n)。空间复杂度与广度优先搜索使用的队列需要的容量相关，为 O(n)。