Java, LeetCode | 366. Find Leaves of Binary Tree

🚀 풀이 후기

Leaf 노드만 찾아서 삭제하는 부분이 까다로웠습니다.

Leaf 노드를 삭제하니 부모 노드도 Leaf 노드라고 착각하게 되는 것을 주의하면서 코드를 짜야합니다.

🌒 문제 설명

Given the root of a binary tree, collect a tree's nodes as if you were doing this:

Collect all the leaf nodes.
Remove all the leaf nodes.
Repeat until the tree is empty.

 

Example 1. 사진

Example 1:

Input: root = [1,2,3,4,5]
Output: [[4,5,3],[2],[1]]
Explanation:
[[3,5,4],[2],[1]] and [[3,4,5],[2],[1]] are also considered correct answers 
since per each level it does not matter the order on which elements are returned.


Example 2:

Input: root = [1]
Output: [[1]]

🌓 문제 풀이

바닥 노드를 삭제한 뒤, 부모 노드가 자식 노드라고 생각하지 않도록 removeLeafNodes() 메서드에서 수정된 TreeNode를 반환하도록 했습니다.

또한, 수정된 노드로 다음 바닥 노드를 모을 수 있도록 (collectLeafNodes()를 수행할 수 있도록) TreeNode root 도 수정해 줬습니다.

노드는 DFS 방법으로 탐색했습니다.

 

DFS(Depth First Search) 깊이 우선 탐색으로 탐색하다 보면, 위 Example1 root = [1,2,3,4,5,6] 은 [4,5,2,3,1]의 순서로 탐색할 수 있습니다.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private List<List<Integer>> answer; // 최종적으로 리턴할 답
    private List<Integer> childList; // answer안에 들어가게 될 Leaf nodes list
    public List<List<Integer>> findLeaves(TreeNode root) {
        answer = new ArrayList<>(); // answer 이차원 리스트를 초기화합니다.
        while(root != null){ // root가 null이 될 때까지 반복합니다.
            childList = new ArrayList<>(); // 하위 list를 초기화합니다.
            collectLeafNodes(root); // 바닥 노드들을 모읍니다.
            answer.add(childList); // answer에 모은 노드들을 추가합니다.
            root = removeLeafNodes(root); // 바닥 노드들을 삭제합니다.
        }
        return answer; // 최종 결과를 반환합니다.
    }

    private void collectLeafNodes(TreeNode root){
        if(root == null){ // root가 null이면 리턴합니다.
            return;
        }
        if(root.left==null && root.right == null){ // root의 자식 노드들이 null이면 모읍니다.
            childList.add(root.val);
            return;
        }
        collectLeafNodes(root.left); // 왼쪽 노드들을 탐색합니다.
        collectLeafNodes(root.right); // 오른쪽 노드들을 탐색합니다.
    }

    private TreeNode removeLeafNodes(TreeNode root){
        if(root == null){ // root가 null이면 그대로 반환합니다.
            return root;
        }
        if(root.right == null && root.left == null){ // root의 자식 노드들이 null이면 삭제하기 위해 null을 반환합니다.  
            return null;
        }
        root.left = removeLeafNodes(root.left); // 현재 노드의 왼쪽 자식 노드에 삭제한 정보를 저장합니다.
        root.right = removeLeafNodes(root.right); // 현재 노드의 오른쪽 자식노드에 삭제된 정보를 저장합니다.
        return root; // 수정된 노드를 반환합니다.
    }
}

 

N: 노드 개수

- 시간복잡도: O(2N)

- 공간복잡도: O(N)

 

🌕 리팩토링

Leaf노드를 찾고 삭제하는 과정을 한 번에 수행하도록 변경했습니다.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private List<List<Integer>> answer;
    private List<Integer> childList;
    public List<List<Integer>> findLeaves(TreeNode root) {
        answer = new ArrayList<>();
        while(root != null){
            childList = new ArrayList<>();  
            root = dfs(root);    
             answer.add(childList);        
        }
        return answer;
    }

    private TreeNode dfs(TreeNode root){
        if(root == null){
            return root;
        }
        if(root.right == null && root.left == null){     
             childList.add(root.val);
            return null;
        }
        root.left = dfs(root.left);
        root.right = dfs(root.right);
        return root;
    }
}

- 시간복잡도: O(N)

- 공간복잡도: O(N)

---

리트코드 문제

깃허브 코드