[编程题]按之字形顺序打印二叉树

```public static ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
int layer = 1;
//s1存奇数层节点
Stack<TreeNode> s1 = new Stack<TreeNode>();
s1.push(pRoot);
//s2存偶数层节点
Stack<TreeNode> s2 = new Stack<TreeNode>();

ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();

while (!s1.empty() || !s2.empty()) {
if (layer%2 != 0) {
ArrayList<Integer> temp = new ArrayList<Integer>();
while (!s1.empty()) {
TreeNode node = s1.pop();
if(node != null) {
System.out.print(node.val + " ");
s2.push(node.left);
s2.push(node.right);
}
}
if (!temp.isEmpty()) {
layer++;
System.out.println();
}
} else {
ArrayList<Integer> temp = new ArrayList<Integer>();
while (!s2.empty()) {
TreeNode node = s2.pop();
if(node != null) {
System.out.print(node.val + " ");
s1.push(node.right);
s1.push(node.left);
}
}
if (!temp.isEmpty()) {
layer++;
System.out.println();
}
}
}
return list;
}```

```	/**
* 大家的实现很多都是将每层的数据存进ArrayList中，偶数层时进行reverse操作，
* 在海量数据时，这样效率太低了。
* （我有一次面试，算法考的就是之字形打印二叉树，用了reverse，
* 直接被鄙视了，面试官说海量数据时效率根本就不行。）
*
* 下面的实现：不必将每层的数据存进ArrayList中，偶数层时进行reverse操作，直接按打印顺序存入
*     1)可用做队列,实现树的层次遍历
*     2)可双向遍历,奇数层时从前向后遍历，偶数层时从后向前遍历
*/
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
if (pRoot == null) {
return ret;
}
ArrayList<Integer> list = new ArrayList<>();
boolean leftToRight = true;

while (queue.size() != 1) {
TreeNode node = queue.removeFirst();
if (node == null) {//到达层分隔符
Iterator<TreeNode> iter = null;
if (leftToRight) {
iter = queue.iterator();//从前往后遍历
} else {
iter = queue.descendingIterator();//从后往前遍历
}
leftToRight = !leftToRight;
while (iter.hasNext()) {
TreeNode temp = (TreeNode)iter.next();
}
list.clear();
continue;//一定要continue
}
if (node.left != null) {
}
if (node.right != null) {
}
}

return ret;
}
```

```class Solution {
public:
vector<vector<int> > Print(TreeNode* pRoot) {
vector<vector<int>> res;
if(pRoot == NULL)
return res;
queue<TreeNode*> que;
que.push(pRoot);
bool even = false;
while(!que.empty()){
vector<int> vec;
const int size = que.size();
for(int i=0; i<size; ++i){
TreeNode* tmp = que.front();
que.pop();
vec.push_back(tmp->val);
if(tmp->left != NULL)
que.push(tmp->left);
if(tmp->right != NULL)
que.push(tmp->right);
}
if(even)
std::reverse(vec.begin(), vec.end());
res.push_back(vec);
even = !even;
}
return res;
}

};```

# python solution:

``````
class Solution:
def Print(self, pRoot):
if not pRoot:
return []
nodeStack=[pRoot]
result=[]
while nodeStack:
res = []
nextStack=[]
for i in nodeStack:
res.append(i.val)
if i.left:
nextStack.append(i.left)
if i.right:
nextStack.append(i.right)
nodeStack=nextStack
result.append(res)
returnResult=[]
for i,v in enumerate(result):
if i%2==0:
returnResult.append(v)
else:
returnResult.append(v[::-1])
return returnResult
``````

```class Solution {
public:
vector<vector<int> > Print(TreeNode* pRoot) {
vector<vector<int> > result;
stack<TreeNode *> stack1,stack2;
bool direction = true;//向右打印为true，向左打印为false
if(pRoot!=NULL)
stack1.push(pRoot);
struct TreeNode *node;
while(!stack1.empty() || !stack2.empty()){
vector<int> data;
if(!stack1.empty()){
while(!stack1.empty()){
node = stack1.top();
stack1.pop();
data.push_back(node->val);
if(node->left!=NULL)
stack2.push(node->left);
if(node->right!=NULL)
stack2.push(node->right);
}
result.push_back(data);
}
else if(!stack2.empty()){
while(!stack2.empty()){
node = stack2.top();
stack2.pop();
data.push_back(node->val);
if(node->right!=NULL)
stack1.push(node->right);
if(node->left!=NULL)
stack1.push(node->left);
}
result.push_back(data);
}
}
return result;
}```

```/*按层序遍历分层打印的代码，添加一段判断用以倒序输出即可*/
public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if(pRoot == null){
return result;
}
boolean leftToRight = true;
ArrayList<Integer> layerList = new ArrayList<Integer>();
int start = 0, end = 1;
while(!layer.isEmpty()){
TreeNode cur = layer.remove();
start++;
if(cur.left!=null){
}
if(cur.right!=null){
}
if(start == end){
end = layer.size();
start = 0;
if(!leftToRight){
}else{
}
leftToRight = !leftToRight;
layerList = new ArrayList<Integer>();
}
}
return result;
}
private ArrayList reverse(ArrayList<Integer> layerList) {
int length = layerList.size();
ArrayList<Integer> reverseList = new ArrayList<Integer>();
for(int i = length-1; i >= 0;i--){
}
return reverseList;
}```

```class Solution {
public:
vector<vector<int> > Print(TreeNode* pRoot) {
vector<vector<int>> res;
if (pRoot == NULL)
return res;
vector<TreeNode*> q1;
vector<TreeNode*> q2;
q1.push_back(pRoot);
bool model = true;//ture表示方向从左向右
while (!q1.empty()){
q2 = q1;
q1.clear();
vector<int> row;
while (!q2.empty()){//把当前层全部访问，并将孩子按一定顺序入栈
TreeNode *temp = q2.back();
q2.pop_back();
row.push_back(temp->val);
if (model == true){//turew为从左向右
if (temp->left) q1.push_back(temp->left);
if (temp->right) q1.push_back(temp->right);
}
else{//false为从右向左
if (temp->right) q1.push_back(temp->right);
if (temp->left) q1.push_back(temp->left);
}
}
model = !model;//变换方向
res.push_back(row);
}
return res;
}
}; ```

``` vector<vector<int> > Print( TreeNode* pRoot)
{
vector<vector<int> > result;
if( pRoot != NULL)
{
stack<TreeNode*> stack1, stack2;
stack1.push( pRoot);
while(!stack1.empty() || !stack2.empty() )
{
vector<int> ret1,ret2;
TreeNode* cur = NULL;
while( !stack1.empty())
{
//偶数行放栈2
cur = stack1.top();
if( cur->left)
stack2.push(cur->left);
if(cur->right)
stack2.push(cur->right);
ret1.push_back(stack1.top()->val);  //保存奇数行数据
stack1.pop();
}
if(ret1.size())
result.push_back(ret1);

while( !stack2.empty())
{
//奇数行放栈1
cur = stack2.top();
if(cur->right)
stack1.push( cur->right);
if(cur->left)
stack1.push( cur->left);

ret2.push_back(stack2.top()->val); //保存偶数行数据
stack2.pop();
}
if(ret2.size())
result.push_back(ret2);
}

}
return result;
}

```

```class Solution {
public:
vector<vector<int> > Print(TreeNode* pRoot) {
vector<vector<int> > ret;
if(pRoot) stk1.push(pRoot);
while(!stk1.empty()||!stk2.empty()){
vector<int> tmp;
while(!stk1.empty()){
TreeNode* node = stk1.top();
tmp.push_back(node->val);
if(node->left) stk2.push(node->left);
if(node->right) stk2.push(node->right);
stk1.pop();
}
if(tmp.size()) ret.push_back(tmp);
tmp.clear();
while(!stk2.empty()){
TreeNode* node = stk2.top();
tmp.push_back(node->val);
if(node->right) stk1.push(node->right);
if(node->left) stk1.push(node->left);
stk2.pop();
}
if(tmp.size()) ret.push_back(tmp);
}
return ret;
}
private:
stack<TreeNode*> stk1;
stack<TreeNode*> stk2;
};```

```类似层次遍历，加个判断条件，奇数层正序遍历，偶数层倒序遍历队列。
public class Solution {
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> layers = new ArrayList<ArrayList<Integer>>();
if (pRoot == null)
return layers;

queue.offer(pRoot);
int depth = 0;
while (!queue.isEmpty()) {
depth ++;
ArrayList<Integer> layer = new ArrayList<Integer>();
int cur = 0, size = queue.size();
if ((depth & 1) == 0) { //如果是偶数层倒序添加
Iterator<TreeNode> it = queue.descendingIterator();
while (it.hasNext()) {
}
}
else { //如果是奇数层正序添加
Iterator<TreeNode> it = queue.iterator();
while (it.hasNext()) {
}
}
while (cur < size) {
TreeNode node = queue.poll();

if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}

cur ++;
}
}
return layers;
}
}```

```    def Print(self, pRoot):
if pRoot == None:
return []
else:
result = []
node_list = [pRoot]
row = 1
while node_list != []:
child_list = []
row_list = []
for i in node_list:
row_list.append(i.val)
if i.left != None:
child_list.append(i.left)
if i.right != None:
child_list.append(i.right)
node_list = child_list
if row %2 == 0:
row_list.reverse()
result.append(row_list)
row += 1
return result```

```        如果C语言写还要自己写个栈么...
/*
* 题目：Z字形打印二叉树
*
* 思路:
* 借助两个栈stack1,stack2.
* 先让首节点接入stack1，然后奇数行时stack1中节点的孩子出队列加入stack2（按先左孩子再右孩子的顺序），并加入链中
* 偶数行时出stack2中节点的孩子加入stack1(按先右孩子后左孩子的顺序)，并加入链
*/
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot)
{
ArrayList<ArrayList<Integer>> zTreeList = new ArrayList<>();

if(pRoot == null)
{
return zTreeList;
}

Stack<TreeNode> oddStack = new Stack<>();//奇数行栈
Stack<TreeNode> evenStack = new Stack<>();//偶数行栈

boolean isOdd = true;

while(!(oddStack.isEmpty() && evenStack.isEmpty()))
{//树没有遍历完
ArrayList<Integer> currentList = new ArrayList<>();

if(isOdd == true)
{//奇数行，stack1中节点的孩子节点按先左孩子后右孩子的顺序入栈2

while(!oddStack.isEmpty())
{
TreeNode currentNode = oddStack.peek(); //取队栈顶元素

if(currentNode.left != null)
{
evenStack.push(currentNode.left);
}

if(currentNode.right != null)
{
evenStack.push(currentNode.right);
}

oddStack.pop(); //栈顶元素出栈

}

isOdd = false; //更新下一层扫描树为偶数行
}
else
{//偶数行,stack2中元素节点的孩子按先右孩子孩子后左孩子顺序入stack1
while(!evenStack.isEmpty())
{
TreeNode currentNode = evenStack.peek(); //获取栈顶元素

if(currentNode.right != null)
{
}

if(currentNode.left != null)
{
}

evenStack.pop();
}

isOdd = true;
}
}

return zTreeList;
}```

``````class Solution {
public:
vector<vector<int> > Print(TreeNode* pRoot) {
vector<vector<int> >  v1, v2;
if(!pRoot) return v1;
vector<int> num; num.push_back(1);
queue<TreeNode* > q;
q.push(pRoot);
int k = 0, all = 0, cnt = 0;
vector<int> tmp;
while(!q.empty()){
TreeNode* op = q.front(); q.pop();
if(op->left) {cnt++; q.push(op->left);}
if(op->right) {cnt++; q.push(op->right);}
if(all < num[k]){tmp.push_back(op->val); all++;}
if(all == num[k]) {v1.push_back(tmp); tmp.clear(); all = 0;
k++; num.push_back(cnt); cnt = 0;}
}
for(int i = 0; i < v1.size(); i++)
if(i % 2 == 1){
vector<int> tp;
for(int j = v1[i].size()-1; j >= 0; j--) tp.push_back(v1[i][j]);
v2.push_back(tp);
}else v2.push_back(v1[i]);
return v2;
}
``````

```//思路1：利用reserve()函数反转
class Solution {
public:
vector<vector<int> > Print(TreeNode* pRoot) {
vector<vector<int>> res;
if(!pRoot)return res;
queue<TreeNode*> que;    //建立个单向队列，用于存放节点
bool flag=false;     //判断是否为偶数行,flag=false代表奇数行，flag=true代表偶数行
que.push(pRoot);
while(que.size()>0){
vector<int> vec;    //行容器，用于存入当前行输出的结果
int len=que.size();
for(int i=0;i<len;i++){
TreeNode* tmp=que.front();
vec.push_back(tmp->val);
que.pop();
if(tmp->left)que.push(tmp->left);
if(tmp->right)que.push(tmp->right);
}
if(flag) reverse(vec.begin(),vec.end());  //是偶数行就反转顺序
flag=!flag;     //改变flag的值
res.push_back(vec);
}
return res;
}
};
---------------------------------------------------------------
//思路2：利用两个栈分别存储奇数行和偶数行
class Solution {
public:
vector<vector<int> > Print(TreeNode* pRoot) {
vector<vector<int>> res;
if(!pRoot)return res;
stack<TreeNode*> sta1;    //建立两个栈，栈1用于存放奇数行节点，栈2用于存放偶数行节点
stack<TreeNode*> sta2;
sta1.push(pRoot);
vector<int> vec;    //行容器，用于存入当前行输出的结果
while(!sta1.empty()||!sta2.empty()){
if(sta2.empty()&&!sta1.empty()){
int len_1=sta1.size();
for(int i=0;i<len_1;i++){
TreeNode* tmp=sta1.top();
vec.push_back(tmp->val);
sta1.pop();
if(tmp->left)sta2.push(tmp->left);    //栈2存放偶数行节点，按照从左子节点到右子节点的顺序push
if(tmp->right)sta2.push(tmp->right);
}
res.push_back(vec);
vec.clear();
}

if(sta1.empty()&&!sta2.empty()){
int len_2=sta2.size();
for(int i=0;i<len_2;i++){
TreeNode* tmp=sta2.top();
vec.push_back(tmp->val);
sta2.pop();
if(tmp->right)sta1.push(tmp->right);    //栈1存放奇数行节点，按照从右子节点到左子节点的顺序push
if(tmp->left)sta1.push(tmp->left);
}
res.push_back(vec);
vec.clear();
}
}
return res;
}
};```

```public class Solution {
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {

ArrayList<ArrayList<Integer> > listAll = new ArrayList<>();
if(pRoot==null)return listAll;
Stack<TreeNode> s1 = new Stack<>();
Stack<TreeNode> s2 = new Stack<>();
int level = 1;
s1.push(pRoot);
while(!s1.isEmpty()||!s2.isEmpty()){
ArrayList<Integer> list = new ArrayList<>();
if(level++%2!=0){
while(!s1.isEmpty()){
TreeNode node = s1.pop();
if(node.left!=null)s2.push(node.left);
if(node.right!=null)s2.push(node.right);
}
}
else{
while(!s2.isEmpty()){
TreeNode node = s2.pop();
if(node.right!=null)s1.push(node.right);
if(node.left!=null)s1.push(node.left);
}
}
}
return listAll;
}
}

```

```# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
from collections import deque
class Solution:
def Print(self, pRoot):
if not pRoot:
return []
result = []
tmp = []
last = pRoot #记录每层的最后一个结点，方便层序遍历换行
left_to_right = True
next_level_node_LtoR = deque([pRoot]) #初始化下一层所有节点的队列，起初为只有根结点
while next_level_node_LtoR: #当下一层不为空时
current_node = next_level_node_LtoR.popleft() #不停从下层队列左边弹出
tmp.append(current_node.val) #将弹出结点放入tmp中
if current_node.left:
next_level_node_LtoR.append(current_node.left)
if current_node.right:
next_level_node_LtoR.append(current_node.right)
if current_node == last: #当运行到最后一个结点，给result赋值当前行的所有元素，也就是tmp
if left_to_right:
result.append(tmp)
else: #若该行应该为从右到左，则倒序append
result.append(tmp[::-1])
tmp = [] #清空tmp，以便下一层继续使用
left_to_right = not left_to_right #调整此项，颠倒下一行的输出顺序
if next_level_node_LtoR: #更新下一行的last结点，如果下一行已经没有元素就会退出
last = next_level_node_LtoR[-1]
return result```

```import java.util.*;

/*
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>> res = new ArrayList<ArrayList<Integer>>();
if (pRoot == null) {
return res;
}
boolean fromLeftToRight = true;
Stack<Integer> stack = new Stack<>();
while (!list.isEmpty()) {
int left = 0;
int right = list.size();
ArrayList<Integer> tmp = new ArrayList<>();
while (left++ < right) {
// Node cur = list.pollFirst();
if(fromLeftToRight) {
TreeNode cur = list.pollFirst();
if(cur.left != null) {
}
if(cur.right != null) {
}
}
else {
TreeNode cur = list.pollFirst();
stack.push(cur.val);
if(cur.left != null) {
}
if(cur.right != null) {
}
}
}
while (!fromLeftToRight && !stack.isEmpty()) {
}
fromLeftToRight = !fromLeftToRight;
}
return res;
}
}
```

```'''

'''
class Solution:
def Print(self, pRoot):
# write code here
if pRoot == None:
return []
falg = 0 # 0表示从左往右，1表示从右往左
node_list = [[pRoot]]
result = []
while node_list:
current_nodes = node_list[0] # 当前层的节点
node_list = node_list[1:]
new_nodes = [] # 下一层的节点，按照从左往右的顺序存储
res = [] # 当前层得到的输出
while len(current_nodes) > 0:
# 从左往右
if falg == 0:
res.append(current_nodes[0].val)
if current_nodes[0].left != None:
new_nodes.append(current_nodes[0].left)
if current_nodes[0].right != None:
new_nodes.append(current_nodes[0].right)
current_nodes = current_nodes[1:]
# 从右往左
else:
res.append(current_nodes[-1].val)
if current_nodes[-1].right != None:
new_nodes.insert(0, current_nodes[-1].right)
if current_nodes[-1].left != None:
new_nodes.insert(0, current_nodes[-1].left)
current_nodes = current_nodes[:-1]
result.append(res)
falg = 1 - falg
if new_nodes:
node_list.append(new_nodes)
return result```

```/*
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 == NULL)
return result;
stack<TreeNode* > Stack[2];
int current = 0;
int next = 1;
Stack[current].push(pRoot);
vector<int> temp;
while(!Stack[0].empty() || !Stack[1].empty())
{
TreeNode* pNode = Stack[current].top();
temp.push_back(pNode->val);
Stack[current].pop();
if(current == 0)
{
if(pNode->left != NULL)
{
Stack[next].push(pNode->left);
}
if(pNode->right != NULL)
{
Stack[next].push(pNode->right);
}
}
else{
if(pNode->right != NULL)
{
Stack[next].push(pNode->right);
}
if(pNode->left != NULL)
{
Stack[next].push(pNode->left);
}
}
if(Stack[current].empty())
{
result.push_back(temp);
temp.clear();
current = 1 - current;
next = 1- next;
}
}
return result;
}

};

```

import java.util.*;

/*
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>> res = new ArrayList<>();
if (pRoot == null) {
return res;
}
Stack<Integer> stack = new Stack<>(); //保存每层
ArrayList<Integer> list = new ArrayList<>();
TreeNode last = pRoot;
TreeNode nlast = null;
boolean l2r = true; //是否按从左到右顺序打印
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
stack.push(node.val);
if (node.left != null) {
nlast = node.left;
}
if (node.right != null) {
nlast = node.right;
}
if (node == last) {
last = nlast;
if (!l2r) {
int size = stack.size();
for (int i = 0; i < size; i++) {
}

l2r = true;
} else {
l2r = false;
}
stack = new Stack<>();
list = new ArrayList<>();

}
}
return res;
}

}

912条回答 59562浏览

# 通过挑战的用户

• 2019-08-23 18:29:49
• 2019-08-23 18:29:10
• 2019-08-23 18:20:44
• 2019-08-23 18:18:21
• 2019-08-23 17:51:04

# 相关试题

• 扫描二维码，关注牛客网

• 下载牛客APP，随时随地刷题