404. Sum of Left Leaves

문제)

404. Sum of Left Leaves

 

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

A leaf is a node with no children. A left leaf is a leaf that is the left child of another node.

 

Example 1:

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

 

솔루션1)

- DFS를 이용해서 방문한 노드의 자식이 없는 경우 leaf로 인식

- 추가적으로 왼쪽 leaf를 찾아야하므로 재귀함수에 direction을 주어서 왼쪽 자식인지, 오른쪽 자식인지 값을 넘겨서 왼쪽 leaf의 경우만 체크해야 함

class Solution:
    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:        
        LEFT = 0
        RIGHT = 1
        def dfs(node, direction):
            if node is None:
                return 0
            
            # 자식이 없는 leaf and 왼쪽 노드
            if node.left is None and node.right is None and direction == LEFT:                
                return node.val
            
            return dfs(node.left, LEFT) + dfs(node.right, RIGHT)
        
        return dfs(root, -1)

솔루션2)

-  솔루션1 코드 개선

class Solution:
    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:                
        def dfs(node, is_left):
            if node is None:
                return 0
            
            # 자식이 없는 leaf and 왼쪽 노드
            if node.left is None and node.right is None and is_left:                
                return node.val
            
            return dfs(node.left, is_left=True) + dfs(node.right, is_left=False)
        
        return dfs(root, is_left=False)