脚本宝典收集整理的这篇文章主要介绍了[Leetcode-Tree]Sum of Left Leaves，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
Sum of Left Leaves
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.
1.解题思路
这个题目其实就是基于先序遍历，用递归和非递归思想都可以。
1）非递归：
借助栈，在push节点的时候判断是否是左叶子节点，如果是就累计进sum中。
2）递归：
求所有左叶子节点的和，我们可以将其分解为左子树的左叶子和+右子树的左叶子和
递归结束条件：找到左叶子节点，就可以返回该节点的val。
2.代码
1） 非递归
public class Solution {
Stack<TreeNode> s=new Stack<TreeNode>();
int sum=0;
public int sumOfLeftLeaves(TreeNode root) {
if(root==null) return 0;
pushLeft(root);
while(!s.empty()){
TreeNode node=s.pop();
if(node.right!=null)
pushLeft(node.right);
}
return sum;
}
private void pushLeft(TreeNode root){
TreeNode node=root;
while(node!=null){
s.push(node);
//判断是否为左叶子节点
if(node.left!=null&&node.left.left==null&&node.left.right==null)
sum+=node.left.val;
node=node.left;
}
}
}2)递归
public class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if(root==null) return 0;
int leftsum,rightsum;
if(root.left!=null&&root.left.left==null&&root.left.right==null)
leftsum=root.left.val;
else leftsum=sumOfLeftLeaves(root.left);
rightsum=sumOfLeftLeaves(root.right);
return leftsum+rightsum;
}
}以上是脚本宝典为你收集整理的[Leetcode-Tree]Sum of Left Leaves全部内容，希望文章能够帮你解决[Leetcode-Tree]Sum of Left Leaves所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。