题目

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

方法

方法：双栈实现
参考：https://www.cnblogs.com/rosending/p/5721721.html

思路

使用两个栈，分别存放从左到右，和从右到左输出的节点，因为不是每层节点都是先进左子树再进右子树的
leftToright栈中，打印数值，然后先进左子树，再进右子树，左右子树进到rightToleft栈中
rightToleft栈中，打印数值，然后先进右子树，再进左子树，左右子树进到leftToright栈中

代码

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function Print (pRoot) {
  // write code here
  if (!pRoot) return []
  let result = []
  let lstack = []
  let rstack = []
  lstack.push(pRoot)
  while (lstack.length || rstack.length) {
    let line = []
    if (lstack.length) {
      while (lstack.length) {
        let item = lstack.pop()
        line.push(item.val)
        if (item.left) rstack.push(item.left)
        if (item.right) rstack.push(item.right)
      }
    } else {
      while (rstack.length) {
        let item = rstack.pop()
        line.push(item.val)
        if (item.right) lstack.push(item.right)
        if (item.left) lstack.push(item.left)
      }
    }
    result.push(line)
  }
  return result
}