LeetCode 102 二叉树的层序遍历

1.迭代

• 利用队列的特性，先进先出
• 先放入一个root 节点，然后push到res中

• 之后依次将left 和 right 推到队列中 此次需注意顺序，因为我们需要 left优先 ```javascript /**

  • Definition for a binary tree node.
  • function TreeNode(val) {
  • this.val = val;
  • this.left = this.right = null;
  • } / /*
  • @param {TreeNode} root

  • @return {number[][]} */ var levelOrder = function (root) { if (!root) return []

    const res = []

    const queue = []

    queue.push(root)

    while (queue.length) {

    const temp = []
    let len = queue.length
    while (len--) {
        const node = queue.shift()
        temp.push(node.val)
        if (node.left) queue.push(node.left)
        if (node.right) queue.push(node.right)
    }
    res.push(temp)

    }

    return res }

**时间复杂度：**

- 每个节点在此次都需要进行操作，所以是 **O(n)**

**<br />**空间复杂度：**

- 需要保存每个节点到result中，所以是 **O(n)**
<a name="CoBzX"></a>
## 2. 递归

- 递归使用了 level来记录节点的层级
- 每当当前节点层级等于目前树的最高级时就添加一个空列表
- 然后将该层级的所有元素添加进去
```javascript
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function (root) {
  const result = []
  const helper = function (node, lever) {
    if (result.length === lever) result.push([])

    result[lever].push(node.val)

    if (node.left) helper(node.left, lever + 1)

    if (node.right) helper(node.right, lever + 1)
  }
  if (!root) return []
  helper(root, 0)
  return result
}

时间复杂度：

• 所有节点都被计算过一次，为 O(n)

空间复杂度:**

• 需要一个result 列表来存放转换后的节点 O(n)