首页 > 试题广场 >

按之字形顺序打印二叉树

[编程题]按之字形顺序打印二叉树
  • 热度指数：538076 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）

数据范围：,树上每个节点的val满足
要求：空间复杂度：，时间复杂度：
例如：
给定的二叉树是{1,2,3,#,#,4,5}

该二叉树之字形层序遍历的结果是
[
[1],
[3,2],
[4,5]
]
示例1

输入

{1,2,3,#,#,4,5}

输出

[[1],[3,2],[4,5]]

说明

如题面解释，第一层是根节点，从左到右打印结果，第二层从右到左，第三层从左到右。
示例2

输入

{8,6,10,5,7,9,11}

输出

[[8],[10,6],[5,7,9,11]]
示例3

输入

{1,2,3,4,5}

输出

[[1],[3,2],[4,5]]

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
Alex11296头像 Alex11296 
设两个栈，s1存放奇数层，s2存放偶数层
遍历s1节点的同时按照左子树、右子树的顺序加入s2，
遍历s2节点的同时按照右子树、左子树的顺序加入s1
class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int> >  vec;
        if(pRoot == NULL) return vec;
        stack<TreeNode*> stk1, stk2;
        stk1.push(pRoot);
        vector<int> tmp;
        while(!stk1.empty() || !stk2.empty()){
            while(!stk1.empty()){
                TreeNode* pNode = stk1.top();
                tmp.push_back(pNode->val);
                if(pNode->left) stk2.push(pNode->left);
                if(pNode->right) stk2.push(pNode->right);
                stk1.pop();
            }
            if(tmp.size()){
                vec.push_back(tmp);
                tmp.clear();
            }
            while(!stk2.empty()){
                TreeNode* pNode = stk2.top();
                tmp.push_back(pNode->val);
                if(pNode->right) stk1.push(pNode->right);
                if(pNode->left) stk1.push(pNode->left);
                stk2.pop();
            }
            if(tmp.size()){
                vec.push_back(tmp);
                tmp.clear();
            }
        }
        return vec;
        
    }
    
};

发表于 2018-05-18 10:35:50 回复(1)
牛客168067号头像 牛客168067号 
        如果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;
		
		
		oddStack.add(pRoot);
		
		while(!(oddStack.isEmpty() && evenStack.isEmpty()))
		{//树没有遍历完
			ArrayList<Integer> currentList = new ArrayList<>();
			
			if(isOdd == true)
			{//奇数行，stack1中节点的孩子节点按先左孩子后右孩子的顺序入栈2
				
				while(!oddStack.isEmpty())
				{
					TreeNode currentNode = oddStack.peek(); //取队栈顶元素
					
					currentList.add(currentNode.val); //添加当前列表
					
					if(currentNode.left != null)
					{
						evenStack.push(currentNode.left);
					}
					
					if(currentNode.right != null)
					{
						evenStack.push(currentNode.right);
					}
					
					oddStack.pop(); //栈顶元素出栈
					
				}
				
				zTreeList.add(currentList);//加入当前行
				
				isOdd = false; //更新下一层扫描树为偶数行
			}
			else
			{//偶数行,stack2中元素节点的孩子按先右孩子孩子后左孩子顺序入stack1
				while(!evenStack.isEmpty())
				{
					TreeNode currentNode = evenStack.peek(); //获取栈顶元素
					
					currentList.add(currentNode.val);
				
					if(currentNode.right != null)
					{
						oddStack.add(currentNode.right);
					}
					
					if(currentNode.left != null)
					{
						oddStack.add(currentNode.left);
					}
					
					evenStack.pop();
				}
				
				zTreeList.add(currentList);
				
				isOdd = true;
			}
		}
		
		return zTreeList;
	}

发表于 2015-12-15 10:26:23 回复(6)
不想修改昵称……头像 不想修改昵称……
用两个栈实现，栈s1与栈s2交替入栈出栈。reverse方法时间复杂度比较高，两个栈以空间换时间 


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();
                    list.add(node.val);
                    if(node.left!=null)s2.push(node.left);
                    if(node.right!=null)s2.push(node.right);
                }
            }
            else{
                while(!s2.isEmpty()){
                    TreeNode node = s2.pop();
                    list.add(node.val);
                    if(node.right!=null)s1.push(node.right);
                    if(node.left!=null)s1.push(node.left);
                }
            }
            listAll.add(list);
        }
        return listAll;
   }
}

发表于 2018-03-10 20:04:52 回复(1)
Python
dadada1头像 dadada1 
# -*- 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

发表于 2017-08-10 17:56:45 回复(0)
打工不可能打工的头像 打工不可能打工的 
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;
        LinkedList<TreeNode> list = new LinkedList<>();
        Stack<Integer> stack = new Stack<>();
        list.add(pRoot);
        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();
                    tmp.add(cur.val);
                    if(cur.left != null) {
                        list.add(cur.left);
                    }
                    if(cur.right != null) {
                        list.add(cur.right);
                    }
                } 
                else {
                    TreeNode cur = list.pollFirst();
                    stack.push(cur.val);
                    if(cur.left != null) {
                        list.add(cur.left);
                    }
                    if(cur.right != null) {
                        list.add(cur.right);
                    }            
                }
            }
            while (!fromLeftToRight && !stack.isEmpty()) {
                tmp.add(stack.pop());
            }
            fromLeftToRight = !fromLeftToRight;
            res.add(tmp);
        }
        return res;
    }
}

发表于 2018-08-13 17:53:34 回复(0)
Python
zxlly要offer头像 zxlly要offer 
'''
解法：
利用一个标志变量flag来标记从左往右还是从右往走
如果从左往右，那就从头到尾遍历当前层的节点current_nodes，然后将左孩子和右孩子分别append到一个list new_nodes中
如果从右往前，那就从尾到头遍历当前层的节点current_nodes，然后将右孩子和左孩子分别insert到一个list new_nodes中
这样得到的new_nodes还是从左到右有序的
'''
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

发表于 2018-05-20 15:00:01 回复(0)
Java
njmd929008头像 njmd929008
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;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        Stack<Integer> stack = new Stack<>(); //保存每层
        ArrayList<Integer> list = new ArrayList<>();
        queue.add(pRoot);
        TreeNode last = pRoot;
        TreeNode nlast = null;
        boolean l2r = true; //是否按从左到右顺序打印
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            stack.push(node.val);
            if (node.left != null) {
                queue.add(node.left);
                nlast = node.left;
            }
            if (node.right != null) {
                queue.add(node.right);
                nlast = node.right;
            }
            if (node == last) {
                last = nlast;
                if (!l2r) {
                    int size = stack.size();
                    for (int i = 0; i < size; i++) {
                        list.add(stack.pop());
                    }
                    res.add(list);
                    
                    l2r = true;
                } else {
                    list.addAll(stack);
                    res.add(list);
                    l2r = false;
                }
                stack = new Stack<>();
                list = new ArrayList<>();
           
            }
        }
        return res;
    }

}
发表于 2016-06-29 00:30:08 回复(0)
Java
Foreordination头像 Foreordination 
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 root) {
        if (root == null) {
            return new ArrayList<>();
        }
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            ArrayList<Integer> list = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                list.add(cur.val);
                if (cur.left != null){
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            if (res.size() % 2 == 1) {
                Collections.reverse(list);
            }
            res.add(list);
        }
        return res;
    }

}

发表于 2021-09-01 17:35:27 回复(0)
Python
zkqiang头像 zkqiang 
# Python 解法，用递归遍历每一层节点，并按层数为列表的索引值存为子列表
# 然后把奇数索引的子列表倒序即可

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Print(self, pRoot):
        # write code here
        res = list()
        def Traversal(node, depth=0):
            if not node:
                return True
            if len(res) == depth:
                res.append([node.val])
            else:
                res[depth].append(node.val)
            return Traversal(node.left, depth+1) and Traversal(node.right, depth+1)
        Traversal(pRoot)
        for i, v in enumerate(res):
            if i % 2 == 1:
                v.reverse()
        return res

编辑于 2018-02-17 23:14:03 回复(0)
给点力啊大师兄头像 给点力啊大师兄 
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
//利用栈的特性
public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> results = new ArrayList<>();
        if(pRoot == null)
            return results;
        Deque<TreeNode> deque = new ArrayDeque<>();
        deque.push(pRoot);
        int direction = 0;
        while(!deque.isEmpty()) {
            Deque<TreeNode> temp = deque;
            deque = new ArrayDeque<>();
            ArrayList<Integer> list = new ArrayList<>();
            if(direction == 0) {
                while(!temp.isEmpty()) {
                    TreeNode t = temp.pop();
                    list.add(t.val);
                    if(t.left != null)
                        deque.push(t.left);
                    if(t.right != null)
                        deque.push(t.right);
                }
                results.add(list);
                direction = 1;
            }
            else {
                while(!temp.isEmpty()) {
                    TreeNode t = temp.pop();
                    list.add(t.val);
                    if(t.right != null)
                        deque.push(t.right);
                    if(t.left != null)
                        deque.push(t.left);
                }
                results.add(list);
                direction = 0;
            }
        }
        return results;
    }

}

发表于 2017-10-16 14:42:57 回复(0)
评估未通过头像 评估未通过 
//思路应该都差不多，但是我的代码具体实现得相对简洁一些
class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int> >res;
        if(pRoot == nullptr)
            return res;
        
        queue<TreeNode*> q[2];
        q[0].push(pRoot);
        int i = 0;
        while(q[0].size() != 0 || q[1].size() != 0){
            vector<int> clayer;
            while(q[i].size()){
                TreeNode* pTemp = q[i].front();
                clayer.push_back(pTemp->val);
                if(pTemp->left)
                    q[1-i].push(pTemp->left);
                if(pTemp->right)
                    q[1-i].push(pTemp->right);
                q[i].pop();
            }
            if(i % 2 == 1){
                vector<int> vTemp = clayer;
                size_t size = vTemp.size();
                for(size_t j=0; j<size; ++j)
                    clayer[j] = vTemp[size-j-1];
            }
            res.push_back(clayer);
            i = 1 - i;
        }
        return res;
    } 
};

发表于 2017-07-15 19:12:43 回复(0)
北溟鱼汤头像 北溟鱼汤

解题思路：
利用双端队列，通过控制当前层节点个数，同时保存下一层节点个数，进行层次遍历。
代码稍长，但是比较好理解，就是右边出当前层的节点，从左边进遍历节点左右子节点；同理，左边出当前层的节点时，要从右边进遍历节点的右左子节点。
通过一个boolean变量来控制调用逻辑，感觉比插null节点或者记录层数等方法要方便。

public class Solution {
    public ArrayList> Print(TreeNode pRoot) {
        ArrayList> res = new ArrayList();
        if (pRoot == null) return res;
        Deque deque = new LinkedList();
        deque.add(pRoot);
        int curNums = 1;
        int nextNums = 0;
        boolean flag = true;
        ArrayList list = new ArrayList();
        while(!deque.isEmpty()) {
            if (flag) {
                // 右边出，左边进
                pRoot= deque.removeLast();
                list.add(pRoot.val);
                curNums--;
                if (pRoot.left != null) {
                    deque.addFirst(pRoot.left);
                    nextNums++;
                }
                if (pRoot.right != null) {
                    deque.addFirst(pRoot.right);
                    nextNums++;
                }
            } else {
                // 左边出，右边进
                pRoot= deque.removeFirst();
                list.add(pRoot.val);
                curNums--;
                if (pRoot.right != null) {
                    deque.addLast(pRoot.right);
                    nextNums++;
                }
                if (pRoot.left != null) {
                    deque.addLast(pRoot.left);
                    nextNums++;
                }
            }
            if (curNums == 0) {
                curNums = nextNums;
                nextNums = 0;
                res.add(list);
                list = new ArrayList();
                flag = !flag;
            }
        }

        return res;
    }
}
发表于 2018-06-21 10:21:04 回复(1)
线上幽灵007头像 线上幽灵007 
/*
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;
    }
    
};
上面是剑指offer的答案，上述代码定义了两个栈Stack【0】和Stack【1】，在打印一个栈里的节点时，它的子节点保存到另一个栈里。当一层所有节点都打印完毕时，交换这两个栈并继续打印下一层。
发表于 2018-04-01 16:22:30 回复(0)
Java
荣耀内推王者头像 荣耀内推王者 
import java.util.*;
import java.util.ArrayList;
public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        
        ArrayList<ArrayList<Integer>> res = new ArrayList();
        ArrayList<Integer> valPath = new ArrayList();
        ArrayList<TreeNode> path = new ArrayList();
        ArrayList<TreeNode> temp = new ArrayList();
        boolean flag = true;
        if(pRoot == null) return res;
        temp.add(pRoot);
        valPath.add(pRoot.val);
        res.add(new ArrayList<Integer>(valPath));//不可直接res.add(valPath),之后改变valPath的值，res也会随之改变
        valPath.clear();
        while (temp.size() != 0) {

            for (int i = 0 ; i < temp.size() ; i++) {
                if (temp.get(i).left != null) {
                    path.add(temp.get(i).left);
                    valPath.add(temp.get(i).left.val);
                }
                if (temp.get(i).right != null) {
                    path.add(temp.get(i).right);
                    valPath.add(temp.get(i).right.val);
                }
            }
            if(valPath.size() == 0) break;
            if(flag){
                 Collections.reverse(valPath);
                flag = !flag;
            }else{
                flag = !flag;
            }
            res.add(new ArrayList<Integer>(valPath));
            valPath.clear();
            temp.clear();
            for (int i = 0 ; i < path.size() ; i++) {
                temp.add(path.get(i));
            }
            path.clear();

        }
        return res;

        
    }

}

发表于 2022-07-07 12:54:42 回复(0)
C++
牛客757388365号头像 牛客757388365号
为什么要用栈，在层序遍历的基础上微调就行了 
class Solution {
  public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int>> ans;
        if (!pRoot)
            return ans;
        queue<TreeNode*> que;
        que.push(pRoot);
        bool rev = false;
        while (!que.empty()) {
            int size = que.size();
            vector<int> temp(size);
            if (rev) {
                for (int i = size - 1; i >= 0; --i) {
                    TreeNode* cur = que.front();
                    que.pop();
                    temp[i] = cur->val;
                    if (cur->left)
                        que.push(cur->left);
                    if (cur->right)
                        que.push(cur->right);
                }
            } else {
                for (int i = 0; i < size; ++i) {
                    TreeNode* cur = que.front();
                    que.pop();
                    temp[i] = cur->val;
                    if (cur->left)
                        que.push(cur->left);
                    if (cur->right)
                        que.push(cur->right);
                }
            }
            rev = !rev;
            ans.push_back(temp);
        }
        return ans;
    }
};


发表于 2022-06-13 00:05:30 回复(1)
Java
txy_钟琛头像 txy_钟琛 
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>> ans = new ArrayList<>();
        if (pRoot == null) {
            return ans;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(pRoot);
        boolean flag = true;
        while (!stack.isEmpty()) {
            ArrayList<Integer> list = new ArrayList<>();
            Queue<TreeNode> queue = new ArrayDeque<>();
            while (!stack.isEmpty()) {
                TreeNode cur = stack.pop();
                list.add(cur.val);
                queue.add(cur);
            }
            while (!queue.isEmpty()) {
                TreeNode cur = queue.poll();
                if (flag) {
                    if (cur.left != null) {
                        stack.add(cur.left);
                    }
                    if (cur.right != null) {
                        stack.add(cur.right);
                    }
                } else {
                    if (cur.right != null) {
                        stack.add(cur.right);
                    }
                    if (cur.left != null) {
                        stack.add(cur.left);
                    }
                }
            }
            flag = !flag;
            ans.add(list);
        }
        return ans;
    }
}

发表于 2022-05-29 12:24:27 回复(0)
C++
牛娃牛娃头像 牛娃牛娃 
/*
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>> res;
        queue<TreeNode*> que;
        if(pRoot!=nullptr)que.push(pRoot);
        int count=0;
        while(!que.empty()){
            int size =que.size();
            vector<int> path;
            for(int i=0;i<size;i++){
                
                TreeNode* node =que.front();
                que.pop();
                path.push_back(node->val);
                if(node->left){
                    que.push(node->left);
                }
                if(node->right){
                    que.push(node->right);
                }
            }
            //从0层开始奇数层 反转
            if(count++%2==1){
                reverse(path.begin(),path.end());
                res.push_back(path);
            }else{
                res.push_back(path);
            }
        }
        return res;
    }
    
};
层序遍历+计数翻转
发表于 2022-05-08 15:16:12 回复(0)
offer99999999999头像 offer99999999999

如图，假设某一层顺序访问 5，6，7，则访问的同时插入孩子节点也是顺序插入。但是题目要求上一层顺序访问时，下一层逆序访问，这跟栈的思想一样(插入和访问顺序相反)，所以我们可以用栈来保存插入的孩子节点，访问的时候再从栈顶开始访问即可。

有两个小细节：

  1. 顺序访问时，孩子节点从左往右顺序入栈，先入左孩子再入有孩子；同理，逆序访问时，孩子节点从右往左入栈，先入右孩子再入左孩子。
  2. 访问上一层结点和插入下一层结点不能共用一个栈，理由是插入孩子节点会破坏上层结点访问的顺序。所以每次插入的时候构造一个临时栈，一层全插入完再交换到访问栈中。 
class Solution {
public:
    vector<vector<int>> Print(TreeNode *pRoot) {
        //Z字形访问结果集
        vector<vector<int>> res;
        if (pRoot == nullptr) return res;
        //用栈保存每层节点：结点插入顺序和访问顺序相反
        std::stack<TreeNode *> s;
        s.push(pRoot);
        TreeNode *p;
        //判断这次是先入左孩子还是先入右孩子
        bool isReverse = false;
        while (!s.empty()) {
            int len = s.size();
            res.emplace_back();
            //临时插入栈
            stack<TreeNode *> temp;
            for (int i = 0; i < len; ++i) {
                p = s.top();
                s.pop();
                res.back().emplace_back(p->val);
                if (isReverse) {
                    if (p->right) temp.push(p->right);
                    if (p->left) temp.push(p->left);
                } else {
                    if (p->left) temp.push(p->left);
                    if (p->right) temp.push(p->right);
                }
            }
            //将临时栈的数据挪回正式栈
            s.swap(temp);
            //每次改变入栈顺序
            isReverse = !isReverse;
        }
        return res;
    }
};
发表于 2022-03-20 13:53:23 回复(0)
Java
bingogogogogo头像 bingogogogogo
一个双向队列，奇数层队头取元素，队尾入元素，偶数层队尾取元素，对头入元素 
public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        Deque<TreeNode> dq = new LinkedList<>();
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        boolean dir = true;
        if(pRoot != null)
            dq.offerLast(pRoot);
        while(!dq.isEmpty()) {
            int count = dq.size();
            ArrayList<Integer> line = new ArrayList<>();
            while(count-- > 0) {
                TreeNode node;
                if(dir) {
                    node = dq.pollFirst();
                    if(node.left != null)
                        dq.offerLast(node.left);
                    if(node.right != null)
                        dq.offerLast(node.right);
                }
                else {
                    node = dq.pollLast();
                    if(node.right != null)
                        dq.offerFirst(node.right);
                    if(node.left != null)
                        dq.offerFirst(node.left);
                }
                line.add(node.val);
            }
            dir = !dir;
            result.add(line);
        }
        return result;
    }
}


发表于 2022-03-13 18:50:10 回复(0)
C++
等一个offer！头像 等一个offer！ 
/*
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>>res;
        if(pRoot==nullptr) return res;
        queue<TreeNode*>q;
        q.push(pRoot);
        int count=0;
        while(!q.empty()){
            vector<int>tmp;
            int sz = q.size();
            for(int i=0;i<sz;++i){
                TreeNode* cur = q.front();
                q.pop();
                tmp.push_back(cur->val);
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);
            }
            if(count%2 == 0){
                res.push_back(tmp);
            }else{
                reverse(tmp.begin(),tmp.end());
                res.push_back(tmp);
            }
            count++;
        }
        return res;
    }
    
};

发表于 2022-03-10 18:06:17 回复(1)
提交观点

问题信息

栈 队列 树
难度：
1524条回答 118724浏览

热门推荐

通过挑战的用户

相关试题

按之字形顺序打印二叉树

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号