차원 별로 이 진 트 리 인쇄

1990 단어
이 진 트 리 가 있 습 니 다. 알고리즘 을 설계 하여 이 이 진 트 리 를 층 에 따라 인쇄 하 십시오.이 진 트 리 의 뿌리 노드 루트 를 지정 합 니 다. 인쇄 결 과 를 되 돌려 주 십시오. 결 과 는 각 층 의 배열 에 따라 저장 되 고 모든 배열 의 순 서 는 층수 에 따라 위 에서 아래로 내 려 가 며 각 층 의 배열 내 요 소 는 왼쪽 에서 오른쪽으로 배열 되 어 있 습 니 다.보증 결산 점 수 는 500 보다 작다.
사고의 방향
이 진 트 리 를 계층 별로 옮 겨 다 니 면 대기 열 을 이용 하면 이 루어 집 니 다. 단, 계층 별로 인쇄 하려 면 각 층 의 마지막 노드 를 기록 해 야 합 니 다. 여기 서 우 리 는 두 개의 변수 last 와 nLast 를 사용 하여 현재 줄 의 마지막 노드 와 현재 알 고 있 는 마지막 노드 를 각각 기록 해 야 합 니 다. 현재 옮 겨 다 니 는 노드 는 cur 입 니 다.
last 초기 값 은 root 입 니 다. nLast 가 업 데 이 트 를 담당 합 니 다. nLast 는 이미 옮 겨 다 니 는 마지막 노드 를 가리 키 고 있 습 니 다. 대기 열 에 노드 를 추가 할 때마다 nLast 는 이 노드 를 가리 키 고 있 습 니 다. 또한 cur = last 가 되면 last = nLast 를 업데이트 합 니 다.
상위 코드:
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}*/
public class TreePrinter {
    public int[][] printTree(TreeNode root) {
        if(root==null) return null;
        ArrayList> nodes=new ArrayList<>();
        ArrayList curLine=new ArrayList<>();
        Queue queue=new LinkedList<>();
        queue.offer(root);
        TreeNode cur=null,last=root,nLast=null;
        while(!queue.isEmpty()){
            cur=queue.poll();
            curLine.add(cur.val);
            if(cur.left!=null){
                queue.offer(cur.left);
                nLast=cur.left;
            }
            if(cur.right!=null){
                queue.offer(cur.right);
                nLast=cur.right;
            }
            if(cur==last){        //    last,               ,
                nodes.add(curLine);
                last=nLast;
                curLine=new  ArrayList();
            }
        }
        int[][]result=new int[nodes.size()][];
        for(int i=0;i

좋은 웹페이지 즐겨찾기