Gidhub BE Developer

LeetCode : 102. Binary Tree Level Order Traversal

2021-09-26
goodGid
LeetCode

102. Binary Tree Level Order Traversal

Problem

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

Example

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

[1] Code (21. 09. 26)

Need to Retry –> Reference Code 참고

class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {

    if (root == null) {
        return new ArrayList<>();
    }

    Queue<Node> q = new LinkedList<>();
    q.add(new Node(root, 0));

    HashMap<Integer, List<Integer>> map = new HashMap<>();
    int depthSize = 0;

    while (!q.isEmpty()) {
        Node node = q.poll();

        List<Integer> list = map.getOrDefault(node.depth, new ArrayList<>());
        list.add(node.treeNode.val);
        map.put(node.depth, list);

        if (node.treeNode.left != null) {
            q.add(new Node(node.treeNode.left, node.depth + 1));
        }

        if (node.treeNode.right != null) {
            q.add(new Node(node.treeNode.right, node.depth + 1));
        }
    }

    List<List<Integer>> ans = new ArrayList<>();
    int idx = 0;
    while (true) {
        if (!map.containsKey(idx)) {
            break;
        }
        ans.add(new ArrayList(map.get(idx++)));
    }
    return ans;
}

class Node {
    private TreeNode treeNode;
    private int depth;

    public Node(TreeNode treeNode, int depth) {
        this.treeNode = treeNode;
        this.depth = depth;
    }
}
}

Concern Point

HashMap 선언 시 Value에 List 넣기

HashMap<Integer, List<Integer>> map = new HashMap<>();
  • 갑자기 Value에 List 어떻게 넣어야 하지? 생각이 나지 않았다.

Reference Code

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> lvOrder = new ArrayList<>();
        if (root == null) {
            return lvOrder;
        }
        Queue<TreeNode> bfsTreeBuffer = new LinkedList<>();
        bfsTreeBuffer.offer(root);
        while (!bfsTreeBuffer.isEmpty()) {
            int layerSize = bfsTreeBuffer.size(); // [1]
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < layerSize; i++) { // [2]
                TreeNode current = bfsTreeBuffer.poll();
                level.add(current.val);
                if (current.left != null) {
                    bfsTreeBuffer.offer(current.left);
                }
                if (current.right != null) {
                    bfsTreeBuffer.offer(current.right);
                }
            }
            lvOrder.add(level);
        }
        return lvOrder;
    }
}

  • [1] : Binary Tree 특징을 이용하여

    Queue에 들어있는 Size가 해당 Level에 존재하는 Node의 수이다.

  • [2] : 위 특징을 이용하여 [2]에서 Size만큼만 for 문을 돌린다.

Review

  • 구현 문제라 어렵지 않았지만

    다른 사람의 풀이를 보면서 한 수 배웠다.

[2] Code (21. 11. 20) (x)

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }

        List<List<Integer>> ans = new ArrayList<>();

        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);

        while (!q.isEmpty()) {
            int size = q.size();

            List<Integer> tempAns = new ArrayList<>();

            for (int i = 0; i < size; i++) {
                TreeNode node = q.poll();
                tempAns.add(node.val);

                if (node.left != null) {q.add(node.left);}
                if (node.right != null) {q.add(node.right);}
            }
            ans.add(tempAns);
        }

        return ans;
    }
}

Review

  • 문제를 보자마자 아이디어가 떠올랐다.

    다시 풀어볼 필요는 없어 보인다.

[3] Code (24. 01. 21) (x)

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return new LinkedList<>();
        }
        List<List<Integer>> ans = new LinkedList<>();
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        
        while (!q.isEmpty()) {
            int size = q.size();
            
            List<Integer> _ans = new ArrayList<>();
            for (int i=0; i<size; i++) {
                TreeNode node = q.poll();
                _ans.add(node.val);
                if (node.left != null) {
                    q.add(node.left);
                }
                if (node.right != null) {
                    q.add(node.right);
                }
            }
            ans.add(_ans);
        }
        
        return ans;
    }
}

Review

  • 저번에도 그렇게 이번에도 문제를 보자마자 쓰윽 풀었다.

    다시 풀어볼 필요는 없어 보인다.

Reference

Recommend

Index