.leetcode(404. Sum of Left Leaves)

https://leetcode.com/problems/sum-of-left-leaves/

 

1. 2022.03.30 시도

소요시간: 12분(iterative), 5분(recursive)

// iterative
class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        
        int sum = 0;
        if (root.left != null) {
            int left = sumOfLeftLeaves(root.left);
            if (root.left.left == null && root.left.right == null) {
                sum = left + root.left.val;
            } else {
                sum += left;
            }
        }
        
        if (root.right != null) {
            int right = sumOfLeftLeaves(root.right);
            sum += right;
        }
        
        
        return sum;
    }
}

// recursive
class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) {
            return 0;
        }
        

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int sum = 0;
        while(!queue.isEmpty()) {
            int size = queue.size();
            for (int i=0; i<size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                    if ((node.left.left == null) && (node.left.right == null)) {
                       sum += node.left.val;  
                    }
                    
                }
                
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        
        return sum;
    }
}

풀이 접근 과정

왼쪽인 것을 알고 있어야하므로 왼쪽을 넘길 때, 계산을 해주어야했다.

 

느낀점

• 처음에는 왼쪽끝에 노드 합인가 했는데 leaf라는 단서를 늦게 봐서 시간이 조금 지났다.

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형