题目地址(404. 左叶子之和)

https://leetcode-cn.com/problems/sum-of-left-leaves/

题目描述

  1. 计算给定二叉树的所有左叶子之和。
  3. 示例：
  5.     3
  6.    / \
  7.   9  20
  8.     /  \
  9.    15   7
  11. 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

前置知识


公司

  • 暂无

思路

注意左叶子 而不是在左侧的节点
如果左节点不为空，且左节点没有左右孩子，那么这个节点就是左叶子

关键点


代码

  • 语言支持：Java

Java Code:

  2. /**
  3.  * Definition for a binary tree node.
  4.  * public class TreeNode {
  5.  *     int val;
  6.  *     TreeNode left;
  7.  *     TreeNode right;
  8.  *     TreeNode() {}
  9.  *     TreeNode(int val) { this.val = val; }
  10.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  11.  *         this.val = val;
  12.  *         this.left = left;
  13.  *         this.right = right;
  14.  *     }
  15.  * }
  16.  */
  17. class Solution {
  18.         //1. 递归返回值为左右子树相加的和 参数为节点 不需要变
  19.         public int sumOfLeftLeaves(TreeNode root) {
  20.             //2. 递归中止条件 节点为空返回0
  21.             if (root == null) {
  22.                 return 0;
  23.             }
  24.             int left = sumOfLeftLeaves(root.left);
  25.             int right = sumOfLeftLeaves(root.right);
  26.             int num = 0 ;
  27.             //3.递归每层的逻辑判断 是以根节点为中心 左儿子!=null 左儿子的左右儿子都=null 这时将他的值赋给num
  28.             if (root.left != null && root.left.right == null && root.left.left == null) {
  29.                 num = root.left.val;
  30.             }
  31.             //有左叶子节点就加上这个值 没有就加0
  32.             return left + right +num;
  33.         }
  34.     }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：404. 左叶子之和 - 图1#card=math&code=O%28n%29&id=D9hGO)
  • 空间复杂度：404. 左叶子之和 - 图2#card=math&code=O%28n%29&id=umNfj)