剑指offer面试题系列

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

分析

初拿到这道题时，觉得这道题好难啊，没有办法下手。但是想起了一句话，要理性的思考问题。所以就按照如下的过程去思考了一下问题。

分层遍历时，肯定是先遍历出来根节点，然后遍历左右孩子。但是接下来怎么能实现只遍历左结点的左右孩子，然后再遍历右结点的左右孩子呢？

开始想到了递归，仔细再一想只能沿着一个节点的左右孩子，然后再左右孩子。。。一直不停的遍历下去，不能实现按层遍历，显然是不行的。于是打消了这个想法。

这两天做的题很多是与栈这个结构有关系的，于是想到了栈这个结构，但是考虑到栈是后入先出的，所以不能按照左右的顺序遍历出来。

顺着这个思路想到了队列。bang!

选定了这个结构接下来就是怎么实现的问题了，在纸上进行了反复试验之后，确定了这个思路：根节点入队，根节点出队时，将其左右孩子入队，左右孩子出队时，分别再将其左右孩子的左右孩子入队，以此类推，直到节点为null。这样想来是递归加队列的实现。

代码实现

package alg.tree;

import java.util.ArrayDeque;
import java.util.ArrayList;

class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.data = val;
        this.left = this.right = null;
    }
}

public class Tree {
    private static ArrayDeque<TreeNode> queue = new ArrayDeque<TreeNode>();
    private static int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    /* 按照层遍历二叉树 */
    public static void TraverseTreeByLayer(TreeNode root) {
        if (root == null)
            return;
        if (queue.isEmpty())
            queue.offer(root);

        TreeNode p = queue.poll();
        System.out.println(p.data);

        if (p.left != null)
            queue.offer(p.left);
        if (p.right != null)
            queue.offer(p.right);

        TraverseTreeByLayer(p.left);
        TraverseTreeByLayer(p.right);
    }

        // 根据数组创建二叉树
    public static TNode BuildTree(int[] arr) {
        ArrayList<TNode> nodelist = new ArrayList<TNode>();
        if (arr == null)
            return null;
        if (arr.length == 1) { // 如果数组中只有一个元素
            TNode root = new TNode(arr[0]);
            return root;
        }

        // 将数组转化成二叉树结点
        for (int i = 0; i < arr.length; i++) {
            nodelist.add(new TNode(arr[i]));
        }

        TNode root = nodelist.get(0);
        for (int j = 0; j < arr.length / 2 - 1; j++) {
            nodelist.get(j).left = nodelist.get(2 * j + 1);
            nodelist.get(j).right = nodelist.get(2 * j + 2);
        }

        int lastParentIndex = arr.length / 2 - 1;
        nodelist.get(lastParentIndex).left = nodelist
                .get(2 * lastParentIndex + 1);
        if (arr.length % 2 == 1) //只有数组长度为奇数时最后一个有孩子的结点才有右孩子
            nodelist.get(lastParentIndex).right = nodelist
                    .get(2 * lastParentIndex + 2);

        return root;
    }

    public static void main(String[] args) {
        TreeNode root = BuildTree(arr);
        TraverseTreeByLayer(root);
    }
}

备注

关于利用数组建立二叉树的函数，在后来的使用中出现了问题，注意到当时疏忽了最后一个有孩子的节点的孩子是不是左右孩子都有的问题。针对此，做出了修改，同时为了程序的健壮性，还考虑了输入的数组中只含有一个元素的问题。

总结

查询了JDK api的文档之后，了解到了 Java 中的队列可以使用ArrayDeque这个类来实现。入队可以使用offer函数或者add函数，出队可以使用poll函数。