网站跟app的区别是什么意思,个人网页设计背景图片素材,最近国际新闻大事20条,wordpress 分类目录 标签转换器#x1f468;#x1f4bb;博客主页#xff1a;花无缺 欢迎 点赞#x1f44d; 收藏⭐ 留言#x1f4dd; 加关注✅! 本文由 花无缺 原创 收录于专栏 【力扣题解】 文章目录 【力扣题解】P404-左叶子之和-Java题解#x1f30f;题目描述#x1f4a1;题解#x1f30f;总结… 博客主页花无缺 欢迎 点赞 收藏⭐ 留言 加关注✅! 本文由 花无缺 原创 收录于专栏 【力扣题解】 文章目录 【力扣题解】P404-左叶子之和-Java题解题目描述题解总结 【力扣题解】P404-左叶子之和-Java题解
P404.左叶子之和
题目描述
给定二叉树的根节点 root 返回所有左叶子之和。
示例 1 输入: root [3,9,20,null,null,15,7]
输出: 24
解释: 在这个二叉树中有两个左叶子分别是 9 和 15所以返回 24示例 2:
输入: root [1]
输出: 0提示:
节点数在 [1, 1000] 范围内-1000 Node.val 1000
题解
深度优先搜索
public int sumOfLeftLeaves(TreeNode root) {return root null ? 0 : dfs(root);
}
// 深度优先搜索
public static int dfs(TreeNode node) {int res 0;// 递归搜索左子树if (node.left ! null) {// 如果当前左子树是叶子节点就累加节点值// 如果不是叶子节点就继续递归遍历该节点res isLeafNode(node.left) ? node.left.val : dfs(node.left);}// 递归搜索右子树// 如果当前右子树不是叶子节点就递归遍历右子树if (node.right ! null !isLeafNode(node.right)) {res dfs(node.right);}return res;
}
// 判断节点是否是叶子节点
// 如果当前节点的左右子树都为空, 那么该节点就是叶子节点
public static boolean isLeafNode(TreeNode node) {return node.left null node.right null;
}广度优先搜索
public int sumOfLeftLeaves(TreeNode root) {// 空树if (root null) {return 0;}int res 0;QueueTreeNode queue new LinkedList();queue.offer(root);while (!queue.isEmpty()) {int len queue.size();while (len-- 0) {TreeNode node queue.poll();// 左子树不为空if (node.left ! null) {// 左子树是叶子节点, 则累加节点值if (isLeafNode(node.left)) {res node.left.val;// 不是叶子节点, 将节点加入队列} else {queue.offer(node.left);}}// 右子树不空if (node.right ! null) {// 右子树不是叶子节点, 将节点加入队列if (!isLeafNode(node.right)) {queue.offer(node.right);}}}}return res;
}时间复杂度均为O(n)树的所有节点都要遍历一次节点数为 n。
总结
这个题的解题思路遍历 判断。
遍历遍历二叉树的所有节点判断判断当前节点是否是左子节点以及是否是叶子节点
只要一个节点满足判断中的两个条件那么我们就可以将当前节点的节点值累加起来如果当前节点是右子节点或者不是叶子节点那么我们就继续递归的遍历它就可以得到最终的答案。
作者花无缺(huawuque404.com) 欢迎关注我的博客花无缺-每一个不曾起舞的日子都是对生命的辜负~ 一起进步-刷题专栏【力扣题解】 往期精彩好文 【CSS选择器全解指南】 【HTML万字详解】 你们的点赞 收藏⭐ 留言 关注✅ 是我持续创作输出优质内容的最大动力 谢谢
