[LeetCode 103 ]二叉树之字形（Z字型）遍历

港控/mmm° 2022-01-23 05:37 109阅读 0赞

题目：按照z字形层次遍历二叉树（以根节点所在层为第1层，则第二层的变量从右边节点开始直到最左边节点，第三层遍历则是从最左边开始到最右边）  
思路：z字形层次遍历是对层次遍历加上了一个限制条件（即相邻层，从左到右的遍历顺序相反），因此还是可以采用队列来实现，只不过节点接入队列时需要考虑加入的顺序  
code:

public class Solution {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            if(root == null){
                return result;
            }
            LinkedList<TreeNode> queue = new LinkedList<>();
            int depth = 0;
            queue.offer(root);
            while(!queue.isEmpty()){
                int size = queue.size();
                List<Integer> tmp = new ArrayList<>();
                for(int i = 0; i < size; i++){
                    TreeNode node = null;
                    //因为是走z字形，所有相邻两层的节点处理是相反的
                    if(depth%2 == 0){
                        node = queue.pollLast();//获取链表最后一个节点
                        if(node.left != null){
                            queue.offerFirst(node.left);
                        }
                        if(node.right != null){
                            queue.offerFirst(node.right);
                        }
    
                    }else{
                        node = queue.poll();//获取链表第一个节点
                        if(node.right != null){
                            queue.offer(node.right);
                        }
                        if(node.left != null){
                            queue.offer(node.left);
                        }
                    }
                    tmp.add(node.val);
                }
                depth++;
                result.add(tmp);
            }
            return result;
        }
    }