首页 > 试题广场 > 按之字形顺序打印二叉树
[编程题]按之字形顺序打印二叉树
请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。
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) {
						temp.add(node.val);
						System.out.print(node.val + " ");
						s2.push(node.left);
						s2.push(node.right);
					}
				}
				if (!temp.isEmpty()) {
					list.add(temp);
					layer++;
					System.out.println();
				}
			} else {
				ArrayList<Integer> temp = new ArrayList<Integer>();
				while (!s2.empty()) {
					TreeNode node = s2.pop();
					if(node != null) {
						temp.add(node.val);
						System.out.print(node.val + " ");
						s1.push(node.right);
						s1.push(node.left);
					}
				}
				if (!temp.isEmpty()) {
					list.add(temp);
					layer++;
					System.out.println();
				}
			}
		}
		return list;
    }

发表于 2016-08-08 12:12:11 回复(24)
	/**
	 * 大家的实现很多都是将每层的数据存进ArrayList中,偶数层时进行reverse操作,
	 * 在海量数据时,这样效率太低了。
	 * (我有一次面试,算法考的就是之字形打印二叉树,用了reverse,
	 * 直接被鄙视了,面试官说海量数据时效率根本就不行。)
	 * 
	 * 下面的实现:不必将每层的数据存进ArrayList中,偶数层时进行reverse操作,直接按打印顺序存入
	 * 思路:利用Java中的LinkedList的底层实现是双向链表的特点。
	 *     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<>();
    	LinkedList<TreeNode> queue = new LinkedList<>();
    	queue.addLast(null);//层分隔符
    	queue.addLast(pRoot);
    	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.add(temp.val);
				}
				ret.add(new ArrayList<Integer>(list));
				list.clear();
				queue.addLast(null);//添加层分隔符
				continue;//一定要continue
    		}
    		if (node.left != null) {
    			queue.addLast(node.left);
    		}
    		if (node.right != null) {
    			queue.addLast(node.right);
    		}
    	}
    	
    	return ret;
    }
    

发表于 2016-04-10 00:08:54 回复(27)
一次性AC。
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;
    }
    
};

发表于 2017-01-24 11:11:54 回复(19)

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
发表于 2017-10-13 22:24:29 回复(7)
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;
    }

发表于 2015-09-15 16:54:31 回复(17)
Ron头像 Ron
/*按层序遍历分层打印的代码,添加一段判断用以倒序输出即可*/
	public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
		ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
		if(pRoot == null){
			return result;
		}
		boolean leftToRight = true;
		Queue<TreeNode> layer = new LinkedList<TreeNode>();
		ArrayList<Integer> layerList = new ArrayList<Integer>();
		layer.add(pRoot);
		int start = 0, end = 1;
		while(!layer.isEmpty()){
			TreeNode cur = layer.remove();
			layerList.add(cur.val);
			start++;
			if(cur.left!=null){
				layer.add(cur.left);           
			}
			if(cur.right!=null){
				layer.add(cur.right);
			}
			if(start == end){
				end = layer.size();
				start = 0;              
				if(!leftToRight){
					result.add(reverse(layerList));
				}else{
					result.add(layerList);
				}
				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--){
			reverseList.add(layerList.get(i));
		}
		return reverseList;
	}

编辑于 2015-07-23 20:01:10 回复(8)
大家看看这样写有什么问题没,如果面试的话,提前谢谢大神给意见了
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;
	}
}; 

编辑于 2016-08-26 22:55:20 回复(3)
可以用一个队列,一个栈实现
也可用两个栈实现,我用两个栈实现,思路简单一点。

来个图直接解释,





 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;
    }



编辑于 2018-04-30 23:40:10 回复(1)
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;
};

发表于 2017-06-03 22:52:38 回复(0)
类似层次遍历,加个判断条件,奇数层正序遍历,偶数层倒序遍历队列。
public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> layers = new ArrayList<ArrayList<Integer>>();
        if (pRoot == null)
            return layers;
        Deque<TreeNode> queue = new LinkedList<TreeNode>();
        
        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()) {
                    layer.add(it.next().val);
                }
            }
            else { //如果是奇数层正序添加
                Iterator<TreeNode> it = queue.iterator();
                while (it.hasNext()) {
                    layer.add(it.next().val);
                }
            }
            while (cur < size) {
                TreeNode node = queue.poll();
                
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                
                cur ++;
            }
            layers.add(layer);
        }
        return layers;	
    }
}

发表于 2016-09-03 15:16:22 回复(1)
    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

发表于 2017-07-14 17:30:28 回复(0)
        如果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)

我的暴力方法
先用宽度优先搜索按一般的把从左到右的每一层搞出来变成一个二维vector
再把下标为偶数的内部vector倒序即可

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;
    }
发表于 2018-12-29 21:46:21 回复(0)
//思路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;
    }
};

编辑于 2018-06-21 17:30:45 回复(0)
用两个栈实现,栈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 回复(0)
# -*- 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)
'''
解法:
利用一个标志变量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)
/*
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)
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)