Leetcode #107. 이진 트리 레벨 순서 탐색 II

Source: Dev.to

문제

이진 트리의 루트가 주어지면, 노드 값들의 bottom‑up 레벨 순서 순회를 반환한다 (즉, 왼쪽에서 오른쪽으로, 레벨별로 leaf에서 root까지).

예시

• Input: root = [3,9,20,null,null,15,7]
• Input: root = [1]
• Input: root = []

제약 조건

• 트리의 노드 수는 [0, 2000] 범위이다.

토론

재귀 함수를 사용하면 각 레벨을 키로 하여 위에서 아래로 만난 노드 값들의 리스트를 매핑하는 맵을 만들 수 있다. 이 맵을 만든 뒤, 수집된 리스트들을 뒤집어 bottom‑up 순서를 만든다.

솔루션 (Java)

class Solution {
    public HashMap> getRestOfTree(int level, TreeNode t) {
        int value = t.val;
        List root = new ArrayList<>();
        root.add(value);
        HashMap> tree = new HashMap<>();
        tree.put(level, root);

        if (t.left == null && t.right == null) {
            return tree;
        } else {
            int nextLevel = level + 1;
            if (t.left == null) {
                HashMap> rightSubtree = getRestOfTree(nextLevel, t.right);
                tree.putAll(rightSubtree);
                return tree;
            } else if (t.right == null) {
                HashMap> leftSubtree = getRestOfTree(nextLevel, t.left);
                tree.putAll(leftSubtree);
                return tree;
            } else {
                HashMap> leftSubtree = getRestOfTree(nextLevel, t.left);
                HashMap> rightSubtree = getRestOfTree(nextLevel, t.right);
                HashMap> restSubtree = new HashMap<>();

                for (Integer key : leftSubtree.keySet()) {
                    if (rightSubtree.containsKey(key)) {
                        List rightSubtreeList = rightSubtree.get(key);
                        List leftSubtreeList = leftSubtree.get(key);
                        leftSubtreeList.addAll(rightSubtreeList);
                        leftSubtree.replace(key, leftSubtreeList);
                    }
                }

                for (Integer key : rightSubtree.keySet()) {
                    if (!leftSubtree.containsKey(key)) {
                        List rightSubtreeList = rightSubtree.get(key);
                        restSubtree.put(key, rightSubtreeList);
                    }
                }

                tree.putAll(leftSubtree);
                tree.putAll(restSubtree);
                return tree;
            }
        }
    }

    public List> levelOrderBottom(TreeNode root) {
        if (root == null) return new ArrayList<>();
        HashMap> tree = getRestOfTree(1, root);
        List> values = new ArrayList<>();
        for (Integer key : tree.keySet()) {
            List nodes = tree.get(key);
            values.add(nodes);
        }
        Collections.reverse(values);
        return values;
    }
}