0094._Binary_Tree_Inorder_Traversal

发表于 分类于 ， ，

094. Binary Tree Inorder Traversal

难度: Medium

刷题内容

原题连接

内容描述

给定一个二叉树，返回它的中序 遍历。

示例:

1
2
3
4
5
6
7
8
输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,3,2]

解题方案

思路 1 迭代
- 时间复杂度: O(3N)

- 空间复杂度: O(N)

执行用时 :64 ms, 在所有 JavaScript 提交中击败了**97.85%**的用户

内存消耗 :33.7 MB, 在所有 JavaScript 提交中击败了**34.70%**的用户

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
const inorderTraversal = node => {
  const valueList = []
  forEachTree(node)
  return valueList
  function forEachTree (node) {
    if (!node) {
      return
    }
    forEachTree(node.left)
    valueList.push(node.val)
    forEachTree(node.right)
  }
}

思路 2 迭代

  • 时间复杂度: O(N²)
  • 空间复杂度: O(N²)

执行用时 :76 ms, 在所有 JavaScript 提交中击败了**69.05%**的用户

内存消耗 :33.7 MB, 在所有 JavaScript 提交中击败了**36.57%**的用户

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
const inorderTraversal = (node) => {
  const valList = []
  const stack = []
  while (node || stack.length) {
    if (node) {
      stack.push(node)
      node = node.left
    } else {
      node = stack.pop()
      valList.push(node.val)
      node = node.right
    }
  }
  return valList
};