文档章节

【LeetCode】404 Sum of Left Leaves(java实现)

BookShu
 BookShu
发布于 2016/10/12 10:05
字数 454
阅读 249
收藏 0

原题

Find the sum of all left leaves in a given binary tree.
Example:

    3
   / \
  9  20
    /  \
   15   7
There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.

题目要求

题目叫“左叶子节点之和”,题目比较清晰,有一棵树,求出树种所有左叶子节点的和。

解法

解法一:这种解法比较直接,对于这种问题,递归的方式比较容易理解。这里需要注意两点:一,必须是左边的叶子节点;二,如果数只有根节点,根节点不是叶子节点,更不是左叶子节点。

public int sumOfLeftLeaves(TreeNode root, Boolean isLeft) {
    if (root == null) {
        return 0;
    }
    int sum = 0;
    if (root.left != null || root.right != null) {
        sum += sumOfLeftLeaves(root.left, true);
        sum += sumOfLeftLeaves(root.right, false);
    }else if (isLeft) {
        sum += root.val;
    }
    
    return sum;
}

public int sumOfLeftLeaves(TreeNode root) {
    return sumOfLeftLeaves(root, false);
}

解法二:很多人不喜欢递归,认为性能不好,这里我再提供一种非递归的思路。一般来说,想用非递归的思路来实现递归的效果,就是使用栈(stack),因为递归的实现就是潜在地使用了栈的思路。这里,我们只需要使用深度优先的方式来遍历节点,并把所有节点放入栈(push)中,之后再取出(pop)即可。 这里列出别人给出的方法:

public int sumOfLeftLeaves(TreeNode root) {
    if(root == null) return 0;
    int ans = 0;
    Stack<TreeNode> stack = new Stack<TreeNode>();
    stack.push(root);
    
    while(!stack.empty()) {
        TreeNode node = stack.pop();
        if(node.left != null) {
            if (node.left.left == null && node.left.right == null)
                ans += node.left.val;
            else
                stack.push(node.left);
        }
        if(node.right != null) {
            if (node.right.left != null || node.right.right != null)
                stack.push(node.right);
        }
    }
    return ans;
}

© 著作权归作者所有

BookShu
粉丝 31
博文 117
码字总数 86781
作品 0
西安
高级程序员
私信 提问
67. Two Sum II - Input array is sorted - LeetCode

Question 167. Two Sum II - Input array is sorted Solution 题目大意:和Two Sum一样,这里给出的数组是有序的 思路:target - nums[i],这样就实现了降维了 Java实现: 别人的实现: https://l...

yysue
2018/08/16
0
0
LeetCode算法题-Sum of Left Leaves(Java实现)

这是悦乐书的第217次更新,第230篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第85题(顺位题号是404)。找到给定二叉树中所有左叶的总和。例如: 二叉树中有两个左叶,分别...

小川94
01/02
0
0
39. Combination Sum - LeetCode

Question 39. Combination Sum Solution 分析:以candidates = [2,3,5], target=8来分析这个问题的实现,反向思考,用target 8减2,3,5这三个数,等到target为0的时候,所减过的数就是我们要求...

yysue
2018/06/13
0
0
637. Average of Levels in Binary Tree - LeetCode

Question 637. Average of Levels in Binary Tree Solution 思路:定义一个map,层数作为key,value保存每层的元素个数和所有元素的和,遍历这个树,把map里面填值,遍历结束后,再遍历这个map,把每...

yysue
2018/06/23
0
0
443. String Compression - LeetCode

Question 443. String Compression Solution 题目大意:把一个有序数组压缩, 思路:遍历数组 Java实现:

yysue
2018/08/10
0
0

没有更多内容

加载失败,请刷新页面

加载更多

二、Docker

1、Docker - The TLDR(Too Long,Don't Read,Linxu 终端工具 ) Docker是在Linux和Windows上运行的软件。它创建、管理和编排容器。该软件以开源方式开发,在Github上作为Moby开源项目的一部分。...

倪伟伟
23分钟前
2
0
Python猫荐书系列之七:Python入门书籍有哪些?

本文原创并首发于公众号【Python猫】,未经授权,请勿转载。 原文地址:https://mp.weixin.qq.com/s/ArN-6mLPzPT8Zoq0Na_tsg 最近,猫哥的 Python 技术学习群里进来了几位比较特殊的同学:一...

豌豆花下猫
今天
5
0
Guava RateLimiter限流源码解析和实例应用

在开发高并发系统时有三把利器用来保护系统:缓存、降级和限流 缓存 缓存的目的是提升系统访问速度和增大系统处理容量 降级 降级是当服务出现问题或者影响到核心流程时,需要暂时屏蔽掉,待高...

算法之名
今天
13
0
国产达梦数据库与MySQL的区别

背景 由于项目上的需要,把项目实现国产化,把底层的MySQL数据库替换为国产的达梦数据库,花了一周的时间研究了国产的数据库-达梦数据库,它和MySQL有一定的区别,SQL的写法也有一些区别。 ...

TSMYK
今天
2
0
老也有错?35岁程序员是一道坎,横亘在每个技术职场人的心中

随着互联网的高速发展变革,大龄恐惧症越来越多地在技术圈被人讨论。很多程序员在工作5-10年以后,都会开始思考5年、10年甚至更久以后的自己,会是怎样一种生活工作状态,以及是否会被时代抛...

我最喜欢三大框架
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部