二叉树层序遍历

给你二叉树的根节点 root，返回其节点值的层序遍历。(即逐层的从做向右访问所有节点)

*示例1:

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

提示：

• 树中节点数目在范围 [0, 2000] 内
• -1000 <= Node.val <= 1000

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function levelOrder(root: TreeNode | null): number[][] {

};

答案：

方法一：广度优先遍历

const levelOrder = (root) => {
  const ret = [];
  if (!root) {
    return ret;
  }
  
  const queue = [root];
  while (queue.length) {
    const currentLevelSize = queue.length;
    ret.push([]);
    for (let i = 1; i <= currentLevelSize; i++) {
      const node = queue.shift();// 每次遍历完都推出当前层的元素
      ret[ret.length - 1].push(node.val);
      if (node.left) {
        quque.push(node.left);
      }
      if (node.right) {
        queue.push(node.right);
      }
    }
  }
  
  return ret;
}

方法二：深度优先遍历

const dfs = (root, setp, ret) => {
  if (!ret[step]) {
    ret[step] =[];
  }
  ret[step].push(root.val);
  if (root.left) {
    dfs(root.left, step + 1, ret);
  }
  if (root.right) {
    dfs(root.right, step + 1, ret);
  }
  
}

const levelOrder = (root) => {
  const ret = [];
  if (!root) {
    return ret;
  }
  
  return dfs(root, 0, ret);
}