手撸二叉树之左叶子之和

手撸二叉树之左叶子之和

今天给大家带来的关于二叉树相关的算法题是二叉树的左叶子之和，正文如下：

题目

计算给定二叉树的所有左叶子之和。

示例：

/ \ 15 7

解题思路

根据题意，我们可以利用深度优先搜索去遍历整个二叉树，去找到所有的左叶子节点，具体思路如下：

定义一个全局变量用于记录左叶子节点的和；遍历二叉树，如果当前节点的左孩子和右孩子都为 null,并且当前的节点是左子树的节点，则判断这个是一个左叶子节点；反之，则继续遍历该节点的左孩子和右孩子，直到找出左叶子节点；如果当前节点是右子树的节点，并且不为null，则继续遍历该节点的左孩子，右孩子，直到找出左叶子节点；

代码实现

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { int ans = 0; public int sumOfLeftLeaves(TreeNode root) { addLeftLeaves(root); return ans; } public void addLeftLeaves(TreeNode root){ if(root!=null){ TreeNode l=root.left; TreeNode r=root.right; if(l!=null&&l.left==null&&l.right==null){ ans+=l.val; } else{ addLeftLeaves(l); } if(r!=null){ addLeftLeaves(r); } } }}

最后

复杂度分析：

时间复杂度：O(n)，其中 n 是树中的节点个数。空间复杂度：O(n)。空间复杂度与广度优先搜索使用的队列需要的容量相关，为 O(n)。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。