网站建设公司未来发展方向,巧家县住房和城乡建设局网站,免费咨询法律服务,应该双网站文章目录 题目标题和出处难度题目描述要求示例数据范围 解法一思路和算法代码复杂度分析 解法二思路和算法代码复杂度分析 题目
标题和出处
标题#xff1a;左叶子之和
出处#xff1a;404. 左叶子之和
难度
3 级
题目描述
要求
给你二叉树的根结点 root \texttt{ro… 文章目录 题目标题和出处难度题目描述要求示例数据范围 解法一思路和算法代码复杂度分析 解法二思路和算法代码复杂度分析 题目
标题和出处
标题左叶子之和
出处404. 左叶子之和
难度
3 级
题目描述
要求
给你二叉树的根结点 root \texttt{root} root返回所有左叶子之和。
示例
示例 1 输入 root [3,9,20,null,null,15,7] \texttt{root [3,9,20,null,null,15,7]} root [3,9,20,null,null,15,7] 输出 24 \texttt{24} 24 解释二叉树中有两个左叶子结点值分别是 9 \texttt{9} 9 和 15 \texttt{15} 15。
示例 2
输入 root [1] \texttt{root [1]} root [1] 输出 0 \texttt{0} 0
数据范围
树中结点数目在范围 [1, 1000] \texttt{[1, 1000]} [1, 1000] 内 -1000 ≤ Node.val ≤ 1000 \texttt{-1000} \le \texttt{Node.val} \le \texttt{1000} -1000≤Node.val≤1000
解法一
思路和算法
为了计算左叶子之和需要找到二叉树中的所有是左子结点的叶结点并计算这些结点之和。可以使用深度优先搜索实现。
从根结点开始遍历二叉树对于每个结点首先判断其左右子结点是否为空然后对非空子结点执行如下操作。 如果左子结点不为空当左子结点是叶结点时将左子结点的值加到左叶子之和当左子结点不是叶结点时在左子树中继续遍历。 如果右子结点不为空且不是叶结点则在右子树中继续遍历。
上述过程是一个递归的过程递归的终止条件是当前结点为叶结点或者当前结点的非空子结点都为叶结点其余情况都会调用递归。由于只有在访问到的结点的左子结点是叶结点的情况下才会将左子结点值加到左叶子之和因此可以确保每个左叶子都被计算一次且其他结点都不会被计算。
代码
class Solution {public int sumOfLeftLeaves(TreeNode root) {int sum 0;if (root.left ! null) {if (isLeaf(root.left)) {sum root.left.val;} else {sum sumOfLeftLeaves(root.left);}}if (root.right ! null !isLeaf(root.right)) {sum sumOfLeftLeaves(root.right);}return sum;}public boolean isLeaf(TreeNode node) {return node.left null node.right null;}
}复杂度分析 时间复杂度 O ( n ) O(n) O(n)其中 n n n 是二叉树的结点数。每个结点都被访问一次。 空间复杂度 O ( n ) O(n) O(n)其中 n n n 是二叉树的结点数。空间复杂度主要是递归调用的栈空间取决于二叉树的高度最坏情况下二叉树的高度是 O ( n ) O(n) O(n)。
解法二
思路和算法
也可以使用广度优先搜索计算左叶子之和。
广度优先搜索需要使用队列存储待访问的结点初始时将根结点入队列。每次将一个结点出队列首先判断其左右子结点是否为空然后对非空子结点执行如下操作。 如果左子结点不为空当左子结点是叶结点时将左子结点的值加到左叶子之和当左子结点不是叶结点时将左子结点入队列。 如果右子结点不为空且不是叶结点则将右子结点入队列。
当队列为空时遍历结束此时即可得到左叶子之和。
由于只有在访问到的结点的左子结点是叶结点的情况下才会将左子结点值加到左叶子之和因此可以确保每个左叶子都被计算一次且其他结点都不会被计算。
代码
class Solution {public int sumOfLeftLeaves(TreeNode root) {int sum 0;QueueTreeNode queue new ArrayDequeTreeNode();queue.offer(root);while (!queue.isEmpty()) {TreeNode node queue.poll();if (node.left ! null) {if (isLeaf(node.left)) {sum node.left.val;} else {queue.offer(node.left);}}if (node.right ! null) {if (!isLeaf(node.right)) {queue.offer(node.right);}}}return sum;}public boolean isLeaf(TreeNode node) {return node.left null node.right null;}
}复杂度分析 时间复杂度 O ( n ) O(n) O(n)其中 n n n 是二叉树的结点数。每个结点都被访问一次。 空间复杂度 O ( n ) O(n) O(n)其中 n n n 是二叉树的结点数。空间复杂度主要是队列空间队列内元素个数不超过 n n n。
