剑指 Offer 32 - I.II.III 从上到下打印二叉树

I题目描述：

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

解析：

1.BFS方法，首先判断根节点是否为空，如果为空，直接返回空数组
2.定义一个list和队列，队列用来保存节点，list用来保存输出的节点，首先让根节点入队
3.while循环遍历队列，当队列不为空时，把队列中的值curr取出，然后把结点值存放到list中
4.判断该节点的左右子树是否为空，如果不为空，则添加到队列中
5.定义一个数组res，把list转化为数组
6.最后然后数组res即可

Java:

public int[] levelOrder(TreeNode root) {
        if(root == null) {
            return new int[0];
        }
        List<Integer> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            TreeNode curr = queue.poll();
            list.add(curr.val);
            if(curr.left != null) {
                queue.add(curr.left);
            }
            if(curr.right != null) {
                queue.add(curr.right);
            }
        }
        int size = list.size();
        int[] res = new int[size];
        for(int i = 0; i < size; i++) {
            res[i] = list.get(i);
        }
        return res;
    }

JavaScript:

var levelOrder = function(root) {
    if(root === null) {
        return [];
    }
    let res = [];
    let queue = [];
    queue.push(root);
    while(queue.length) {
        let curr = queue.shift();
        res.push(curr.val);
        if(curr.left !== null) {
            queue.push(curr.left);
        }
        if(curr.right !== null) {
            queue.push(curr.right);
        }
    }
    return res;
};

II题目描述：

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

解析：

1.设置res用来保存输出结果，设置队列用来存储二叉树中的元素，队列添加二叉树的根节点
2.遍历队列，直到队列为空，定义size记录queue的长度，即每层节点的个数
3.定义temp用来保存每一层节点，保存成功后添加到res中
4.for循环将queue中的元素添加到temp中，从queue中取出一个节点，把节点存放到list中
然后判断当前节点的左右子节点是否有值，如果有，则添加到queue中
5.把存放了每一层元素的数组temp添加到res中，最后返回res即可

Java:

public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new LinkedList<>();
        if(root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> temp = new ArrayList<>();
            for(int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                temp.add(node.val);
                if(node.left != null) {
                    queue.add(node.left);
                }
                if(node.right != null) {
                    queue.add(node.right);
                }
            }
            res.add(temp);
        }
        return res;
    }

JavaScript:

var levelOrder = function(root) {
    let res = [];
    if(root === null) {
        return res;
    }
    let queue = [];
    queue.push(root);
    while(queue.length) {
        let temp = [];
        for(let i = queue.length; i > 0; i--) {
            let node = queue.shift();
            temp.push(node.val);
            if(node.left !== null) {
                queue.push(node.left);
            }
            if(node.right !== null) {
                queue.push(node.right);
            }
        }
        res.push(temp);
    }
    return res;
};

III题目描述：

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

解析：

1.设置res用来保存输出结果，设置一个队列用来存储二叉树中的元素，队列中添加二叉树的根节点
2.定义isOddNumber用来判断当前的层数是否为奇数层，初始化在第0层，为偶数层
3.while循环遍历队列，直到队列为空，定义size用来记录queue的长度，即每层节点的个数
4.奇偶层总是交替出现的，通过取反操作，判断当前的层数是否为奇偶层，由于isOddNumber初始化为false，所以第一次进来这个while循环取反后为true，符合第一层是奇数层的定义
5.生成一个双端队列temp，用来保存每一层节点，保存成功后添加到res中
6.使用for循环，将queue中的元素按照给定的规则添加到temp中，从queue中取出一个节点
如果是奇数层，那么按顺序添加到双端队列的尾部，如果是偶数层，那么按顺序添加到双端队列的头部
7.判断当前节点的左右子节点是否有值，如果有，则添加到queue中
8.把存放了每一层元素的数组temp添加到res中，最后返回res即可

Java:

public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new LinkedList<>();
        if(root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        boolean isOddNumber = false;
        while(!queue.isEmpty()) {
            int size = queue.size();
            isOddNumber = ! isOddNumber;
            LinkedList<Integer> temp = new LinkedList<>();
            for(int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if(isOddNumber) {
                    temp.addLast(node.val);
                } else {
                    temp.addFirst(node.val);
                }
                if(node.left != null) {
                    queue.add(node.left);
                }
                if(node.right != null) {
                    queue.add(node.right);
                }
            }
            res.add(temp);
        }
        return res;
    }

JavaScript:

var levelOrder = function(root) {
    let res = [];
    if(root === null) {
        return res;
    }
    let flag = 0;
    let queue = [];
    queue.push(root);
    while(queue.length) {
        let temp = [];
        for(let i = queue.length; i > 0; i--) {
            let node = queue.shift();
            temp.push(node.val);
            if(node.left !== null) {
                queue.push(node.left);
            }
            if(node.right !== null) {
                queue.push(node.right);
            }
        }
        if(flag % 2 == 0) {
            res.push(temp);
        } else {
            res.push(temp.reverse());
        }
        flag++;
    }
    return res;
};