매일매일 - LeetCode 102 & 107.두 갈래 나무의 층이 두루 다니다

102. 두 갈래 나무의 층이 두루 다니다

해법1

대기열로 단계:

대기열이 비어 있지 않을 때, 대기열에 있는 원소의 개수를 계산하여 이 층이 순환하는 횟수로..

순서대로 대기열에서 지정한 개수의 노드를 꺼내서subList에 추가하고 좌우 아이를 대기열에 추가합니다..

대기열에 원소가 없을 때까지 1, 2 반복..

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

    Queue<TreeNode> queue = new LinkedList<>();
    List<List<Integer>> list = new LinkedList<>();

    if (root == null)
        return list;

    queue.offer(root);
    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        List<Integer> subList = new LinkedList<>();
        for (int i = 0 ; i < levelSize ; i ++) {
            TreeNode node = queue.poll();
            if ( node.left != null ) queue.offer(node.left);
            if ( node.right != null ) queue.offer(node.right);
            subList.add(node.val);
        }
        list.add(subList);
    }
    return list;
}

해법2

각 계층의 계층은 하나의 노드에만 액세스하고 현재 계층 수 (0부터 시작) 가 결과 세트의 계층 수 (1부터 시작) 보다 크면 새 컬렉션을 생성하여 이중 컬렉션에 추가하고 현재 노드의 값을 해당 계층의 컬렉션에 배치합니다.매번 좌우의 아이를 두루 돌아다니며 층수를 +1.

public List<List<Integer>> levelOrder(TreeNode root) {
   List<List<Integer>> res = new ArrayList<>();
    levelHelper(res, root, 0);
    return res;
}

public void levelHelper(List<List<Integer>> res, TreeNode root, int height) {
    if (root == null) return;
    if (height >= res.size())
        res.add(new LinkedList<>());
    res.get(height).add(root.val);
    levelHelper(res, root.left, height + 1);
    levelHelper(res, root.right, height + 1);
}

107. 두 갈래 나무의 차원 훑어보기 II

이 문제는 두 갈래 나무를 정해서 노드 값이 밑에서 위로 올라가는 차원으로 되돌아간다.(즉, 잎 노드가 있는 층에서 뿌리 노드가 있는 층으로 한 층 한 층 왼쪽에서 오른쪽으로 옮겨간다.)말하자면 층의 순서가 반전되고 각 층의 노드 순서는 변하지 않는다.
따라서 다음 두 해법은 이전 문제와 매우 비슷하다. 단지 서브집합을 넣을 때 순서대로 넣는 것이 아니라 거꾸로 넣는 것이다.

해법1

public List<List<Integer>> levelOrderBottom(TreeNode root) {

    Queue<TreeNode> queue = new LinkedList<>();
    List<List<Integer>> list = new LinkedList<>();

    if (root == null)
        return list;

    queue.offer(root);
    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        List<Integer> subList = new LinkedList<>();
        for (int i = 0 ; i < levelSize ; i ++) {
            TreeNode node = queue.poll();
            if ( node.left != null ) queue.offer(node.left);
            if ( node.right != null ) queue.offer(node.right);
            subList.add((Integer) node.e);
        }
        list.add(0, subList); //  ， 
    }
    return list;
}

해법2

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

// DFS
public void levelMaker(List<List<Integer>> list, TreeNode<Integer> root, int level) {
    if(root == null) return;
    if(level >= list.size()) 
        list.add(0, new LinkedList<Integer>());
    list.get(list.size()-level-1).add(root.e); //  
    levelMaker(list, root.left, level+1);
    levelMaker(list, root.right, level+1);
}

두 갈래 나무의 전차 역력, 중차 역력, 후차 역력에 대한 더 많은 총결산은 매일일련 - LeetCode 144 & 94 & 145를 보십시오.두 갈래 나무의 앞 순서가 두루 다니고, 가운데 순서가 두루 다니고, 뒤 순서가 두루 다니다.
본고는 제가 인터넷의 자료와 자신의 이해를 참고하여 정리한 것입니다. 만약에 잘못된 점이 있다면 여러분의 지적을 매우 환영합니다.