LintCode领扣 题解丨 微软常考题：二叉树的锯齿形层次遍历

给出一棵二叉树，返回其节点值的锯齿形层次遍历（先从左往右，下一层再从右往左，层与层之间交替进行）

在线评测地址：

https://www.lintcode.com/problem/binary-tree-zigzag-level-order-traversal/?utm_source=sc-tianchi-sz0818

样例 1:

输入:{1,2,3}

输出:[[1],[3,2]]

解释:

1           

/ \

2 3

它将被序列化为 {1,2,3}

样例 2:

输入:{3,9,20,#,#,15,7}

输出:[[3],[20,9],[15,7]]

3           

9 20

/  \           

15 7

它将被序列化为 {3,9,20,#,#,15,7}

【题解】

算法：树的层次遍历

层次遍历，可以运用广度遍历的思想实现从上往下的逐层遍历。从头结点开始逐层遍历，开辟一个新队列，让头结点入队并计算此时的长度，每次都将当前层的子节点全部压入队列，然后对下一层的节点进行遍历，再将下一层的子节点压入队列，不断循环，一直遍历到底层，判断的终止条件就是队列不为空。

循环里面，队列头出队，判断其是否有左右子结点，如果有，则将此点的子节点入队，但此时还不需要更新队列的长度，当前队列的长度是每层的长度。当这层的长度减为0时，就说明这层的遍历结束，开始更新长度为下一层的长度。

出队的元素的值按照一层层压入结果数组

因为题目锯齿形遍历

我们用一个isforward标记当前方向，每遍历完一层，如果是反向的，则将这层的节点数组倒序，然后将这层的集合压入结果

复杂度分析

时间复杂度O(n)

n为节点数量

空间复杂度O(n)

存下所有点的信息 n为节点数量

public class Solution

{

/**
 * @param root: A Tree
 * @return: A list of lists of integer include the zigzag level order traversal of its nodes' values.
 */
public List<List<Integer>> zigzagLevelOrder(TreeNode root){
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    if (root == null) {
        return ans;
    }
    Queue<TreeNode> q = new LinkedList<TreeNode>();
    //正反向标志
    boolean isForward = true;
    q.offer(root);
    while (!q.isEmpty()) {
        int size = q.size();
        List<Integer> subList = new ArrayList<Integer>();
        for (int i = 0 ; i < size ; i++) {
            TreeNode treeNode = q.poll();
            subList.add(treeNode.val);
            if (treeNode.left != null) { 
                q.offer(treeNode.left);
            }
            if (treeNode.right != null) {
                q.offer(treeNode.right);
            }
        }
        //根据标志来确认当前层遍历的方向
        if (!isForward) {
            Collections.reverse(subList);//翻转
        }
        ans.add(subList);
        //方向反转
        isForward = !isForward;
    }
    return ans;
}           

}

更多题解参见：给出一棵二叉树，返回其节点值的锯齿形层次遍历（先从左往右，下一层再从右往左，层与层之间交替进行）

LintCode 领扣

​

www.lintcode.com

1           

3           

/  \           

/**
 * @param root: A Tree
 * @return: A list of lists of integer include the zigzag level order traversal of its nodes' values.
 */
public List<List<Integer>> zigzagLevelOrder(TreeNode root){
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    if (root == null) {
        return ans;
    }
    Queue<TreeNode> q = new LinkedList<TreeNode>();
    //正反向标志
    boolean isForward = true;
    q.offer(root);
    while (!q.isEmpty()) {
        int size = q.size();
        List<Integer> subList = new ArrayList<Integer>();
        for (int i = 0 ; i < size ; i++) {
            TreeNode treeNode = q.poll();
            subList.add(treeNode.val);
            if (treeNode.left != null) { 
                q.offer(treeNode.left);
            }
            if (treeNode.right != null) {
                q.offer(treeNode.right);
            }
        }
        //根据标志来确认当前层遍历的方向
        if (!isForward) {
            Collections.reverse(subList);//翻转
        }
        ans.add(subList);
        //方向反转
        isForward = !isForward;
    }
    return ans;
}           

更多题解参见九章算法官网：

https://www.jiuzhang.com/solution/binary-tree-zigzag-level-order-traversal/?utm_source=sc-tianchi-sz0818