*LeetCode-Binary Tree Level Order Traversal

우선 자바 에서 bfs 는 어떤 데이터 구 조 를 사용 하 는 지 모 르 고 quue 를 사용 한 후에 quue 가 어떻게 실현 되 는 지 모 릅 니 다.
자바

Queue queueA = new LinkedList();
Queue queueB = new PriorityQueue();

queue 를 실현 하기 위해 linkedlist 를 사용 하여 우선 순위 가 없 는 단순 한 fifo 를 실현 합 니 다.
queue 의 설명 을 보 세 요. 안에 두 개의 function 이 있 는데 각각 대응 합 니 다.
offer peek poll 은 모두 반환 값 을 가지 고 있 습 니 다.
그 다음 에 while 에서 각 층 의 node 개 수 를 제어 하 는 것 을 주의해 야 합 니 다. 바로 quue 에 현재 몇 개의 node 가 있 습 니 다. 먼저 num 을 가 져 오 는 것 을 기억 하 세 요.

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

        Queue <TreeNode> que = new LinkedList<TreeNode>();
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        if ( root == null)
            return ans;
        que.offer(root);
        while (!que.isEmpty()){
            int num = que.size();
            List <Integer> list = new ArrayList<Integer>();
            for ( int i = 0; i < num; i ++ ){
                if ( que.peek().left != null )
                    que.offer(que.peek().left);
                if ( que.peek().right != null )
                    que.offer(que.peek().right);
                list.add( que.poll().val);
            }
            ans.add(list);
        }
        return ans;
    }
}

재 귀적 방법:

public List<List<Integer>> levelOrderBottom(TreeNode root) {
    LinkedList<List<Integer>> list = new LinkedList<List<Integer>>();
    addLevel(list, 0, root);
    return list;
}

private void addLevel(LinkedList<List<Integer>> list, int level, TreeNode node) {
    if (node == null) return;
    if (list.size()-1 < level) list.addFirst(new LinkedList<Integer>());
    list.get(list.size()-1-level).add(node.val);
    addLevel(list, level+1, node.left);
    addLevel(list, level+1, node.right);
}