剑指offer系列-二叉树的遍历

（一）题目描述

二叉树的遍历方式

法1：层序遍历

class Solution10 {
    public int[] levelOrder(TreeNode root) {
        ArrayList result = new ArrayList<>();
        TreeNode temp;
        if(root==null){
            return result.stream().mapToInt(Integer::intValue).toArray();
        }
        Queue queue = new linkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            temp=queue.poll();
            result.add(temp.val);
            if(temp.left!=null){
                queue.offer(temp.left);
            }
            if(temp.right!=null){
                queue.offer(temp.right);
            }
        }
        return result.stream().mapToInt(Integer::intValue).toArray();
    }
}

二、将树的每一层的元素放进数组，并输出（思路：利用队列的size进行循环）

class Solution10 {
    public List> levelOrder(TreeNode root) {
        List> lists = new ArrayList<>();
        Queue res = new linkedList<>();
        res.offer(root);
        while (!res.isEmpty()){
            ArrayList temp = new ArrayList<>();
            //这一步很妙，因为下面添加了元素也不会影响循环中使用的res.size()
            //利用每一步队列的大小来循环
            for (int i = res.size(); i >0 ; i--) {
                TreeNode node=res.poll();
                temp.add(node.val);
                if(node.left!=null){
                    res.add(node.left);
                }
                if(node.right!=null){
                    res.add(node.right);
                }
            }
            lists.add(temp);
        }
        return lists;
    }
}

三、将二叉树按照‘Z’字型打印（思路：利用二维动态数组的size来判断当前加入的以为动态数组是否需要反转）

class Solution10 {
    public List> levelOrder(TreeNode root) {
        List> lists = new ArrayList<>();
        Queue res = new linkedList<>();
        res.offer(root);
        while (!res.isEmpty()){
            ArrayList temp = new ArrayList<>();
            //这一步很妙，因为下面添加了元素也不会影响循环中使用的res.size()
            //利用每一步队列的大小来循环
            for (int i = res.size(); i >0 ; i--) {
                TreeNode node=res.poll();
                temp.add(node.val);
                if(node.left!=null){
                    res.add(node.left);
                }
                if(node.right!=null){
                    res.add(node.right);
                }
            }
            if(lists.size()%2==1){
                Collections.reverse(temp);
            }
            lists.add(temp);
        }
        return lists;
    }
}