[Leetcode-Tree]Sum of Left Leaves

ashe 发布于2019-08-16 10:26 / 704人阅读

摘要：解题思路这个题目其实就是基于先序遍历，用递归和非递归思想都可以。递归求所有左叶子节点的和，我们可以将其分解为左子树的左叶子和右子树的左叶子和递归结束条件找到左叶子节点，就可以返回该节点的。代码非递归判断是否为左叶子节点递归

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 s=new Stack();
     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;
    }
}

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/69802.html

[Leetcode-Tree] Path Sum I II III

摘要：解题思路利用递归，对于每个根节点，只要左子树和右子树中有一个满足，就返回每次访问一个节点，就将该节点的作为新的进行下一层的判断。代码解题思路本题的不同点是可以不从开始，不到结束。代码当前节点开始当前节点左节点开始当前节点右节点开始 Path SumGiven a binary tree and a sum, determine if the tree has a root-to-lea...

notebin 2019-08-16 10:26 评论0 收藏0
[Leetcode-Tree] Sum Root to Leaf Numbers

摘要：解题思路本题要求所有从根结点到叶子节点的路径和，我们用递归实现。结束条件当遇到叶子节点时，直接结束，返回计算好的如果遇到空节点，则返回数值。 Sum Root to Leaf NumbersGiven a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a numbe...

BigNerdCoding 2019-08-16 10:27 评论0 收藏0
[LeetCode] 404. Sum of Left Leaves

Problem 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 ...

Mr_zhang 2019-08-16 13:49 评论0 收藏0
[Leetcode-Tree]Binary Tree Maximum Path Sum

摘要：但是本题的难点在于，使用递归实现，但是前面的第四种情况不能作为递归函数的返回值，所以我们需要定义两个值，代表单边路径的最大值，用于递归用于和回路的较大值。 Binary Tree Maximum Path SumGiven a binary tree, find the maximum path sum. For this problem, a path is defined as a...

caige 2019-08-16 10:27 评论0 收藏0
[Leetcode-Tree]Maximum / Minimum Depth of Binary T

摘要：解题思路用递归实现很简单，对于每个根节点，最大深度就等于左子树的最大深度和右子树的最大深度的较大值。解题思路本题的注意点在于如果某个根节点有一边的子树为空，那么它的深度就等于另一边不为空的子树的深度，其他的逻辑与上一题相同。 Maximum Depth of Binary TreeGiven a binary tree, find its maximum depth. The maxi...

Thanatos 2019-08-16 10:26 评论0 收藏0