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

2020-05-26

二叉树的锯齿形层次遍历

给定一个二叉树，返回其节点值的锯齿形层次遍历。

（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如:

给定二叉树 [3,9,20,null,null,15,7],

题解:

思路1：闭包广度优先搜索

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var zigzagLevelOrder = function (root) {
  let result = []; // 存结果的
  let handler = (node, i) => { // 处理函数 node是当前节点 i是当前节点的高度
    if (!node) return; // 如果没有值直接return
    if (!result[i]) result[i] = []; // 如果当前高度对应的数组没有 初始化为空数组
    if (i % 2 === 1) { // 当当前高度是1，3，5，7...时 因为要反向所以向前插入
      result[i].unshift(node.val);
    } else { // 当前高度为0 2 4 6...时 直接push
      result[i].push(node.val);
    }
    i++; // 高度加1 遍历下一层 注意 这里的高度都是闭包 每一次处理的高度是互不影响的
    handler(node.left, i); // 遍历左侧
    handler(node.right, i); // 遍历右侧
  }
  handler(root, 0); // 从根节点开始 高度为0
  return result;
};