검지 Offer - 지그재그 순서로 두 갈래 트리 인쇄(Java 구현)
2152 단어 검지offer두 갈래 나무데이터 구조와 알고리즘
제목 설명:
함수는 지그재그로 두 갈래 트리를 인쇄합니다. 즉, 첫 번째 줄은 왼쪽에서 오른쪽으로, 두 번째 줄은 오른쪽에서 왼쪽으로, 세 번째 줄은 왼쪽에서 오른쪽으로, 다른 줄은 이와 같이 인쇄합니다.
사고방식 분석: 1. 두 개의 창고stack1,stack2를 빌려야 한다.2. stack1은 홀수층의 노드 수를 기록하는 데 사용되고, stack2는 짝수층의 노드 수를 기록하는 데 사용된다.3. 시작할 때 먼저 머리 노드를 stack1에 넣고 stack1의 노드를 튀기는 동시에 튀어나온 노드의 좌우 하위 노드를 stack2에 저장하고 (왼쪽 노드를 저장하고 오른쪽 노드를 저장하며) 튀어나온 노드를list 집합에 저장합니다.stack1이 비어 있으면 stack2의 요소가 튀어나오기 시작하고 튀어나온 노드의 좌우 하위 노드를 stack1에 저장합니다(오른쪽 노드를 저장하고 왼쪽 노드를 저장합니다). 튀어나온 노드는list 집합에 저장합니다.
코드는 다음과 같습니다.
import java.util.ArrayList;
import java.util.Stack;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
// :
//
public class Solution {
public ArrayList > Print(TreeNode pRoot) {
ArrayList> alist = new ArrayList<>();
if(pRoot == null){
return alist;
}
Stack stack1 = new Stack<>();
Stack stack2 = new Stack<>();
stack1.push(pRoot);
while(!stack1.empty() || !stack2.empty()){
ArrayList list = new ArrayList<>();
if(!stack1.empty()){
while(!stack1.empty()){
TreeNode temp = stack1.pop();
list.add(temp.val);
if(temp.left != null){
stack2.push(temp.left);
}
if(temp.right != null){
stack2.push(temp.right);
}
}
alist.add(list);
}
else{
while(!stack2.empty()){
TreeNode temp = stack2.pop();
list.add(temp.val);
if(temp.right != null){
stack1.push(temp.right);
}
if(temp.left != null){
stack1.push(temp.left);
}
}
alist.add(list);
}
}
return alist;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
20200326 - 검지offer 면접문제 27: 두 갈래 나무의 거울이솔 위 안에 28문제의 답안이 있는데 어떻게 꼬치는지 모르겠다.간단해....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.