Skip to content

094. Binary Tree Inorder Traversal

难度: Medium

刷题内容

原题连接

内容描述

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

示例:

输入: [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%的用户

/**
 * 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%的用户

/**
 * 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
};


回到顶部