二叉树层序遍历

这篇文章发表于 2023年05月16日,星期二,15:46

给你二叉树的根节点 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); }