[검지 Offer] 32.위에서 아래로 두 갈래 나무를 인쇄하다

면접에서 이 문제를 만났는데 손글씨를 쓰지 않아서 맞히는 것도 힘들었다. 아이고, 정말 익숙하면 공교롭구나.이 문제는 I, II, III, 세 문제로 나뉘는데 첫 번째 문제는 간단한 차원을 두루 훑어보는 것이다. 뒤에 두 문제는 첫 번째 문제의 파생 문제인데 이 문제는 면접 문제로 하기에 매우 적합하다.
I - 두 갈래 나무의 각 노드를 위에서 아래로 간단하게 인쇄하고 같은 층의 노드는 왼쪽에서 오른쪽으로 순서대로 인쇄합니다.
예를 들어 두 갈래 나무를 지정합니다: [3,9,20,null,null,15,7] 3/\9 20/\15 7로 돌아갑니다.
[3,9,20,15,7]
출처: 리코드(LeetCode) 링크:https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof
문제 풀이 사고방식의 두 갈래 나무의 차원 반복, 즉 넓이를 우선적으로 반복한다. 보조 공간만 사용하면 잘 해결되고 차원 반복은 선진적인 것이 분명하기 때문에 대열을 선택하는 것은 틀리지 않다.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] levelOrder(TreeNode root) {
         Queue queue = new LinkedList<>();
         List treeLevel = new ArrayList();

        if(root == null)
            return new int[]{};

        queue.add(root);

        while(!queue.isEmpty()){
            TreeNode node = queue.poll();

            treeLevel.add(node.val);

            if(node.left != null) queue.offer(node.left);
            if(node.right != null) queue.offer(node.right);
        }

        int[] arr = new int[treeLevel.size()];
        
        for(int i=0; i

몇 가지 주의:

Queue는 인터페이스일 뿐입니다. 실현이 필요합니다. 왜냐하면 제가 코드를 칠 때 IDE를 사용하지 않았기 때문입니다. 제가 LinkedList를 사용하겠다고 했는데 그가queue를 직접 사용하면 된다고 하니 땀이..

Queue의remove()와poll() 그리고add()와offer()의 차이점은 전자는 이상을 던지고 뒤에는false만 되돌려준다는 것이다..

돌아다니는 노드도 보조적인 Array List에 넣어야 한다

II. - 층별로 인쇄 - 중간 면접 진제는 위에서 아래로 층별로 두 갈래 트리를 인쇄하고 같은 층의 노드는 왼쪽에서 오른쪽으로 순서대로 인쇄하며 층마다 한 줄로 인쇄한다.
예를 들어 두 갈래 나무를 주면[3,9,20,null,null,15,7],
3/\9 20/\15 7은 다음 단계를 반복합니다.
[ [3], [9,20], [15,7] ]
출처: 리코드(LeetCode) 링크:https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof
LeetCode를 푸는 것이 좋습니다. 적어도 반환 매개 변수 형식 List>를 주었습니다.계층 인쇄는 각 계층을 하나의 List 안에 넣고 요약하는 것입니다.면접을 볼 때 팀의 노드를 다시 리스트에 넣을 생각을 했지만 어떻게 순환하는지 도무지 모르겠다. 렉이 걸렸다. 적어도 이중 순환이 필요하다. 그러나 어떻게 순환해야 팀에 들어간 하위 노드가 들어오지 않을 수 있을까?사고방식은 바로 뒤에서 앞으로 순환하는 것이다. 이때queue의 길이는 팀의 노드의 하위 노드를 포함하지 않는다.

class Solution {
    public List> levelOrder(TreeNode root) {
        Queue queue = new LinkedList<>();
        List> res = new ArrayList<>();

        if(root == null)
            return res;

        queue.add(root);

        while(!queue.isEmpty()){

            List tmp = new ArrayList();

            // ， ，
            // i count， index 
            for(int i = queue.size(); i>0; i--) {
                TreeNode node = queue.poll();

                tmp.add(node.val);

                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }

            res.add(tmp);
        }

        return res;
    }
}

III. 지그재그 인쇄 - 중간 함수는 지그재그 순서에 따라 두 갈래 트리를 인쇄합니다. 즉, 첫 번째 줄은 왼쪽에서 오른쪽으로 인쇄하고, 두 번째 줄은 오른쪽에서 왼쪽으로 인쇄하고, 세 번째 줄은 왼쪽에서 오른쪽으로 인쇄합니다. 다른 줄은 이와 같습니다.
예를 들어 두 갈래 나무를 주면[3,9,20,null,null,15,7],
3/\9 20/\15 7은 다음 단계를 반복합니다.
[ [3], [20,9], [15,7] ]
출처: 리코드(LeetCode) 링크:https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof
문제 풀이 사고방식이라는 문제는 또 이전 문제의 파생 문제이다. 지그재그는 바로 앞뒤로 다음 층에서 뒤로 앞으로 나아가는 것이다. 사고방식은 양방향 대열을 유지하는 것이다. 홀수층은 앞뒤로 나가고 짝수층은 뒤에서 나가는 것이다.

class Solution {
    public List> levelOrder(TreeNode root) {
        Deque queue = new ArrayDeque<>();
        List> res = new ArrayList<>();
        int level = 0;
        
        if(root == null)
            return res;
        
        queue.addFirst(root);
        
        while(!queue.isEmpty()){
           
            List tmp = new ArrayList<>();
            
            for(int i=queue.size(); i>0;i--){
                TreeNode node = (level%2==0)?queue.pollFirst():queue.pollLast();

                tmp.add(node.val);
                
                if(level%2==0){
                   if(node.left != null) queue.addLast(node.left);
                   if(node.right != null) queue.addLast(node.right);
                }else{
                    if(node.right != null) queue.addFirst(node.right);
                    if(node.left != null) queue.addFirst(node.left);                
                }
                
            }
            
            level++;
            res.add(tmp);
        }
        
        return res;
    }
}

주의하다

pollFirst()와 addLast()가 쌍을 이룹니다

짝수층이 먼저add왼쪽 아이, 홀수층이 먼저add오른쪽 아이

2층 순환은 모두 뒤에서 앞으로 하고 순환이 새로 추가된 아이의 노드를 피한다