牛客在线编程101-27 按之字形顺序打印二叉树

雨点打透心脏的1/2处 2023-10-04 20:10 4阅读 0赞

描述  
给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）

数据范围：0 \\le n \\le 15000≤n≤1500,树上每个节点的val满足 |val| <= 1500∣val∣<=1500  
要求：空间复杂度：O(n)O(n)，时间复杂度：O(n)O(n)  
例如：  
给定的二叉树是\{1,2,3,\#,\#,4,5\}

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

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;
            }
    
            Queue<TreeNode> q = new LinkedList<>();
            q.add(pRoot);
    
            boolean order = true;
    
            while (!q.isEmpty()) {
        
                ArrayList<Integer> arr = new ArrayList<Integer>();
                int n = q.size();
    
                for (int i = 0; i < n; i++) {
        
                    TreeNode cur = q.poll();
                    arr.add(cur.val);
                    if (cur.left != null) {
        
                        q.add(cur.left);
                    }
                    if (cur.right != null) {
        
                        q.add(cur.right);
                    }
                }
                
                if(order == false) {
        
                    Collections.reverse(arr);
                }
                order = !order;
                res.add(arr);
            }
            return res;
        }
    
    }