leetcode-144.png
二叉树前序遍历
递归
var preorderTraversal = function(root) {
let res = []
if(!root) return res
var preorder = function(root){
if(!root) return
res.push(root.val)
preorder(root.left)
preorder(root.right)
}
preorder(root)
return res
};
不借助其他函数的写法
var preorderTraversal = function(root) {
let res = []
if(!root) return res
res.push(root.val)
res.push(...preorderTraversal(root.left))
res.push(...preorderTraversal(root.right))
return res
};
时间复杂度
时间复杂度： O(n)
每个节点都访问一次，遍历所有节点所需时间为 O(n)，其中 n 是节点的数量。空间复杂度
空间复杂度： O(h)
递归调用栈的空间复杂度是树的高度 h。在最坏的情况下（树退化成链表），空间复杂度为 O(n)。对于平衡二叉树，空间复杂度为 O(log n)。
非递归
var preorderTraversal = function(root) {
let res = []
if(!root) return res
let stack = [root]
while(stack.length){
let node = stack.pop()
res.push(node.val)
// 先将右子节点压入栈，因为栈是后进先出
// 所以需要先处理左子节点，再处理右子节点
if(node.right) stack.push(node.right)
if(node.left) stack.push(node.left)
}
return res
};
时间复杂度
时间复杂度： O(n)
每个节点都访问一次，遍历所有节点所需时间为 O(n)，其中 n 是节点的数量。空间复杂度
空间复杂度： O(h)
栈的最大深度是树的高度 h。在最坏的情况下（树退化成链表），空间复杂度为 O(n)。对于平衡二叉树，空间复杂度为 O(log n)。
