[검지 offer] 두 갈래 나무를 여러 줄로 프린트하세요.

1589 단어
본고는 나의 개인 블로그: 꼬리 부락에서 시작되었다

제목 설명


위에서 아래로 층별로 두 갈래 트리를 인쇄하고 같은 층의 결점은 왼쪽에서 오른쪽으로 출력합니다.층마다 줄을 출력합니다.

문제 풀이 사고방식


바로 두 갈래 나무의 층계가 두루 돌아다니며 대열로 이루어진다.우리는 두 개의 변수가 필요합니다. 하나의start는 현재 층이 인쇄한 노드의 개수를 기록하고 하나의end는 전 층의 모든 노드의 개수를 기록합니다. start==end일 때, 테이블의 현재 층이 다 훑어보았을 때, 다음 층이 훑어보기 시작할 수 있습니다.

참조 코드

import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    ArrayList > Print(TreeNode pRoot) {
        ArrayList > res = new ArrayList >();
        if(pRoot == null)
            return res;
        ArrayList temp = new ArrayList();
        Queue layer = new LinkedList();
        layer.offer(pRoot);
        int start = 0, end = 1;
        while(!layer.isEmpty()){
            TreeNode node = layer.poll();
            temp.add(node.val);
            start ++;
            if(node.left != null)
                layer.add(node.left);
            if(node.right != null)
                layer.add(node.right);
            if(start == end){
                start = 0;
                res.add(temp);
                temp = new ArrayList();
                end = layer.size();
            }
        }
        return res;
    }
}

좋은 웹페이지 즐겨찾기