Skip to main content

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

题目链接​

二叉树的锯齿形层序遍历

题目​

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

思路​

层序遍历（BFS），根据层数来确定方向。

解题方法​

获取当前层的所有节点，根据方向决定是push还是unshift。

代码​

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var zigzagLevelOrder = function(root) {
  if(root === null) {
    return [];
  }
  const stack = [root];
  const result = [];
  // 0 -> right   1 -> left
  let direction = 0;
  while(stack.length) {
    const layerLenght = stack.length;
    result.push([]);
    for(let i = 0; i < layerLenght; i++) {
      const node = stack.shift();
      if(direction === 0) {
        result[result.length - 1].push(node.val);
      } else {
        result[result.length - 1].unshift(node.val);
      }
      
      if(node.left) stack.push(node.left);
      if(node.right) stack.push(node.right);   
    }
    direction = direction === 0 ? 1 : 0;
  }
  return result;
};

复杂度分析​

  • 时间复杂度：O(n)O(n)。
  • 空间复杂度：O(n)O(n)。