题目描述

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

分析

第一反应可以按照普通的层次遍历然后再把第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
};
复制代码