手撸二叉树之左子树之和
发布于: 3 小时前
Hello, 大家好，今天是我参加 9 月更文的第 7 天，今天给大家带来的关于二叉树相关的算法题是二叉树的左叶子之和，正文如下：
题目
计算给定二叉树的所有左叶子之和。
示例：
复制代码
解题思路
根据题意，我们可以利用深度优先搜索去遍历整个二叉树，去找到所有的左叶子节点，具体思路如下：
定义一个全局变量用于记录左叶子节点的和；
遍历二叉树，如果当前节点的左孩子和右孩子都为 null,并且当前的节点是左子树的节点，则判断这个是一个左叶子节点；反之，则继续遍历该节点的左孩子和右孩子，直到找出左叶子节点；
如果当前节点是右子树的节点，并且不为 null，则继续遍历该节点的左孩子，右孩子，直到找出左叶子节点；
代码实现
复制代码
最后
复杂度分析：
时间复杂度：O(n)，其中 nn 是树中的节点个数。
空间复杂度：O(n)。空间复杂度与广度优先搜索使用的队列需要的容量相关，为 O(n)。
版权声明: 本文为 InfoQ 作者【HelloWorld杰少】的原创文章。
原文链接:【http://xie.infoq.cn/article/4e5443c5e80c03fd3953d9a75】。文章转载请联系作者。
佛系编码 2019.05.13 加入
红鲤鱼与绿鲤鱼与驴。
评论