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