题目描述
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推
分析
第一反应可以按照普通的层次遍历然后再把第2、4、6等等偶数层的结果翻转一下，但是那样子效率太低。
上网查阅可以使用双向队列，即两头都可以进和出。需要从左到右打印的从队列头部进入和弹出，需要从右往左打印的从队列尾部进入和弹出
代码实现
/* function TreeNode(x) { this.val = x; this.left = null; this.right = null; } */ function Print(r) { if(r === null) return []; var ds = []; var dir = "r"; var res = []; ds.unshift(null); ds.unshift(r); while(ds.length > 1) { var temp = []; if(dir === 'r'){ var cur = ds.shift(); while(cur !== null) { temp.push(cur.val); if(cur.left !== null) ds.push(cur.left); if(cur.right !== null) ds.push(cur.right) cur = ds.shift(); } ds.unshift(null); }else{ var cur = ds.pop(); while(cur !== null){ temp.push(cur.val); if(cur.right !== null) ds.unshift(cur.right); if(cur.left !== null) ds.unshift(cur.left); cur = ds.pop(); } ds.push(null); } res.push(temp); dir = dir === "r" ? "l" : "r"; } return res; } module.exports = { Print : Print };
