검지offer의 지그재그 순서로 두 갈래 나무 인쇄
18663 단어 검지 OFFER
검지offer의 지그재그 순서로 두 갈래 나무 인쇄
제목 설명
함수는 지그재그로 두 갈래 트리를 인쇄합니다. 즉, 첫 번째 줄은 왼쪽에서 오른쪽으로, 두 번째 줄은 오른쪽에서 왼쪽으로, 세 번째 줄은 왼쪽에서 오른쪽으로, 다른 줄은 이와 같이 인쇄합니다.
문제 풀이 사고방식
나는 아마도 책을 보고 멍청한 것 같다. 책의 방법이 헷갈려서 창고를 쓰고 싶을 때, 왼쪽 나무를 먼저 저장하고 오른쪽 나무를 다음 층에 저장하고 반대로, 다행히 마지막에 냉정하게 분석하고 홀수층의 순서가 두루 흐르고, 짝수층은 창고를 사용한다.처음에 빈 바늘이 들어오는 상황을 주의하십시오.세그먼트 오류를 일으키다.
Code
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
vector<vector<int> > Print(TreeNode* pRoot) {
vector<vector<int> > result;
if(!pRoot) return result;
vector<int> layer;
queue<TreeNode*> q;
stack<int> temps;
int currentLayerCount = 1, nextLayerCount = 0, flag = 0;
q.push(pRoot);
while(!q.empty()) {
TreeNode* currentTreeNode = q.front();
q.pop();
currentLayerCount--;
if(flag) {
temps.push(currentTreeNode->val);
} else {
layer.push_back(currentTreeNode->val);
}
if(currentTreeNode->left) {
q.push(currentTreeNode->left);
nextLayerCount++;
}
if(currentTreeNode->right) {
q.push(currentTreeNode->right);
nextLayerCount++;
}
if(!currentLayerCount) {
currentLayerCount = nextLayerCount;
nextLayerCount = 0;
if(flag) {
while(!temps.empty()) {
layer.push_back(temps.top());
temps.pop();
}
}
result.push_back(layer);
layer.clear();
flag = 1-flag;
}
}
return result;
}
};
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Collections;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer> > result = new ArrayList<ArrayList<Integer> >();
if(pRoot != null) {
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(pRoot);
int currentCount = 1, currentLevel = 0, nextLayerCount = 0;
ArrayList<Integer> layer = new ArrayList<Integer>();
while(queue.size() > 0) {
TreeNode currentNode = queue.peek();
queue.pop();
layer.add(currentNode.val);
currentCount--;
if(currentNode.left != null) {
nextLayerCount++;
queue.add(currentNode.left);
}
if(currentNode.right != null) {
nextLayerCount++;
queue.add(currentNode.right);
}
if(currentCount == 0) {
currentCount = nextLayerCount;
nextLayerCount = 0;
if(currentLevel % 2 == 1) {
Collections.reverse(layer);
}
currentLevel++;
result.add(layer);
layer = new ArrayList<Integer>();
}
}
}
return result;
}
}
총결산
reverse
좋음ArrayList
중 무작위 접근용get(index)
방법, 부치용set(index, value)
방법Collections.reverse(list)
좋아요