LeetCode - Easy - 404. Sum of Left Leaves

Love The Way You Lie 2022-10-16 08:50 43阅读 0赞

## Topic ##

*  Tree

## Description ##

[https://leetcode.com/problems/sum-of-left-leaves/][https_leetcode.com_problems_sum-of-left-leaves]

Given the root of a binary tree, return the sum of all left leaves.

**Example 1:**

![bd91113354db1d62fb4ed5a980c45a63.png][]

Input: root = [3,9,20,null,null,15,7]
    Output: 24
    Explanation: There are two left leaves in the binary tree, with values 9 and 15 respectively.

**Example 2:**

Input: root = [1]
    Output: 0

**Constraints:**

*  The number of nodes in the tree is in the range \[1, 1000\].
 *  \-1000 <= Node.val <= 1000

## Analysis ##

核心：前序遍历二叉树。

方法一：递归法。

方法二：迭代法。

## Submission ##

import java.util.LinkedList;
    
    import com.lun.util.BinaryTree.TreeNode;
    
    public class SumOfLeftLeaves { 
    	
    	//方法一：递归法
        public int sumOfLeftLeaves(TreeNode root) { 
        	if(root == null) return 0;
        	int temp = 0;
        	if(root.left != null && root.left.left == null && root.left.right == null)
        		temp = root.left.val;
        	
        	return temp + sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
        }
        
        //方法二：迭代法
        public int sumOfLeftLeaves2(TreeNode root) { 
            if(root == null) return 0;
            int ans = 0;
            LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
            stack.push(root);
            
            while(!stack.isEmpty()) { 
                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;
        }
        
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    import com.lun.util.BinaryTree;
    
    public class SumOfLeftLeavesTest { 
    
    	@Test
    	public void test() { 
    		SumOfLeftLeaves obj = new SumOfLeftLeaves();
    
    		assertEquals(24, obj.sumOfLeftLeaves(BinaryTree.integers2BinaryTree(3, 9, 20, null, null, 15, 7)));
    		assertEquals(0, obj.sumOfLeftLeaves(BinaryTree.integers2BinaryTree(1)));
    		
    		
    		assertEquals(24, obj.sumOfLeftLeaves2(BinaryTree.integers2BinaryTree(3, 9, 20, null, null, 15, 7)));
    		assertEquals(0, obj.sumOfLeftLeaves2(BinaryTree.integers2BinaryTree(1)));
    	}
    }

[https_leetcode.com_problems_sum-of-left-leaves]: https://leetcode.com/problems/sum-of-left-leaves/
[bd91113354db1d62fb4ed5a980c45a63.png]: /images/20221014/9b475b17b04349b685f2eb28b23b5681.png