나무의 최대 너비 구하 기 (차원 달력)

2260 단어 데이터 구조
이 진 트 리 너비: 대기 열 을 사용 하여 이 진 트 리 를 옮 겨 다 닙 니 다.이전 층 을 옮 겨 다 니 며 완성 한 후, 다음 층 의 모든 노드 는 이미 대열 에 놓 여 있 습 니 다. 이때 대열 의 요소 개 수 는 다음 층 의 너비 입 니 다.이 를 통 해 다음 층 을 차례로 옮 겨 다 니 면 이 진 트 리 의 최대 폭 을 구 할 수 있다.어떻게 층 층 이 갈 라 집 니까?하나의 변수 len 으로 현재 층 의 결산 점 수 를 기록 하고 하나의 결산 점 을 내 면 len –, len = = 0 일 때 순환 을 종료 한 다음 에 대기 열 에 있 는 노드 수 를 len 에 할당 합 니 다.
 int getWidth(BiNode head) {    
     if(head==null)    
         return 0;    
     int max=1;    
     LinkedListll=new LinkedList();    
        ll.add(head);    
        while(true){    
            int len=ll.size();   //          
            if(len==0)  //   ,          
                break;    
            while(len>0){    
                BiNode b=ll.poll();    
                len--;         -1, 0    
                if(b.left!=null)    
                    ll.add(b.left);    
                if(b.right!=null)    
                    ll.add(b.right);    
            }    
            max=Math.max(max, ll.size());              
        }    
        return max;    
    }  

좋은 웹페이지 즐겨찾기