二叉树——404. 左叶子之和
1 题目描述
给定二叉树的根节点 root ，返回所有左叶子之和。
2 题目示例
在这里插入图片描述
示例 2:
输入: root = [1] 输出: 0
3 题目提示
节点数在 [1, 1000] 范围内 -1000 <= Node.val <= 1000
4 思路
一个节点为「左叶子」节点，当且仅当它是某个节点的左子节点，并且它是一个叶子结点。因此我们可以考虑对整棵树进行遍历，当我们遍历到节点node时，如果它的左子节点是一个叶子结点，那么就将它的左子节点的值累加计入答案。 深度： 复杂度分析
- 时间复杂度:o(n)，其中n是树中的节点个数。
- 空间复杂度:O(n)。空间复杂度与深度优先搜索使用的栈的最大深度相关。在最坏的情况下，树呈现链式结构，深度为O(n)，对应的空间复杂度也为O(n)。 广度： 复杂度分析
- 时间复杂度:O(n)，其中n是树中的节点个数。
- 空间复杂度:O(n)。空间复杂度与广度优先搜索使用的队列需要的容量相关，为O(n)。
递归： 递归的遍历顺序为后序遍历(左右中)，是因为要通过递归函数的返回值来累加求取左叶子数值之和。。 递归三部曲:
确定递归函数的参数和返回值 判断一个树的左叶子节点之和，那么一定要传入树的根节点，递归函数的返回值为数值之和，所以为int 使用题目中给出的函数就可以了。
确定终止条件 依然是
if (root NLLL) return O ;确定单层递归的逻辑 当遇到左叶子节点的时候，记录数值，然后通过递归求取左子树左叶子之和，和右子树左叶子之和，相加便是整个树的左叶子之和。
5 我的答案
深度：
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
return root != null ? dfs(root) : 0;
}
public int dfs(TreeNode node) {
int ans = 0;
if (node.left != null) {
ans += isLeafNode(node.left) ? node.left.val : dfs(node.left);
}
if (node.right != null && !isLeafNode(node.right)) {
ans += dfs(node.right);
}
return ans;
}
public boolean isLeafNode(TreeNode node) {
return node.left == null && node.right == null;
}
}广度：
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
int ans = 0;
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node.left != null) {
if (isLeafNode(node.left)) {
ans += node.left.val;
} else {
queue.offer(node.left);
}
}
if (node.right != null) {
if (!isLeafNode(node.right)) {
queue.offer(node.right);
}
}
}
return ans;
}
public boolean isLeafNode(TreeNode node) {
return node.left == null && node.right == null;
}
}普通递归：
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if (root == null) return 0;
int leftValue = sumOfLeftLeaves(root.left); // 左
int rightValue = sumOfLeftLeaves(root.right); // 右
int midValue = 0;
if (root.left != null && root.left.left == null && root.left.right == null) { // 中
midValue = root.left.val;
}
int sum = midValue + leftValue + rightValue;
return sum;
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-07-25，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
