103. 二叉树的锯齿形层序遍历

一、思路

是在二叉树层次遍历的基础上的改进，添加一个控制层数的变量。奇数层从头部添加，偶数层从尾部添加。从而实现锯齿形层序遍历。

二、代码实现

var zigzagLevelOrder = function(root) {
    // 定义一个队列用于存储每个节点的左右子树, 定义一个存储最后结果的数组
    var queue=[], result = [];
    
    // 判空操作,j为空树
    if(!root) return result;
    
    // 初始化队列，将根节点存储
    queue.push(root);
    // 用来控制每一层遍历的方向
    var j = 0;
    
    // 每次将每一层的元素弹出队列的时候，需要将这一层的所有元素全部弹出。
    // 每次弹出元素的时候，要检查这个元素的左右子树是否存在
    while(queue.length){
        // 定义一个存储每一层元素的数组
        const arr = [];
        
        // 用n来控制每一层弹出的元素。当队列当中有几个元素，就要弹出多少元素。因为这个队列当中的元素是上一层节点的左右子节点。
        const n = queue.length;        
        for(let i=0;i<n;i++){
            // 从队头弹出元素
            var node = queue.shift();
            
            // 添加条件判断，奇数层从头部添加，偶数层从尾部添加
            if(j%2 == 0){
                arr.push(node.val);
            }else{                           
                arr.unshift(node.val); 
            }

            // 检查这个元素的左右子树是否存在.存在就放进队列当中
            if(node.left) queue.push(node.left);
            if(node.right) queue.push(node.right); 
        } 
        // 每一层的元素遍历结束之后，存储到最后的结果中。
        result.push(arr);
        j = j + 1;
    }
    return result;
};