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
};
不借助其他函數(shù)的寫法
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
};
時間復(fù)雜度
時間復(fù)雜度： O(n)
每個節(jié)點(diǎn)都訪問一次装畅，遍歷所有節(jié)點(diǎn)所需時間為 O(n)，其中 n 是節(jié)點(diǎn)的數(shù)量。空間復(fù)雜度
空間復(fù)雜度： O(h)
遞歸調(diào)用棧的空間復(fù)雜度是樹的高度 h并徘。在最壞的情況下（樹退化成鏈表），空間復(fù)雜度為 O(n)扰魂。對于平衡二叉樹麦乞，空間復(fù)雜度為 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)
// 先將右子節(jié)點(diǎn)壓入棧劝评，因?yàn)闂Ｊ呛筮M(jìn)先出
// 所以需要先處理左子節(jié)點(diǎn)姐直，再處理右子節(jié)點(diǎn)
if(node.right) stack.push(node.right)
if(node.left) stack.push(node.left)
}
return res
};
時間復(fù)雜度
時間復(fù)雜度： O(n)
每個節(jié)點(diǎn)都訪問一次，遍歷所有節(jié)點(diǎn)所需時間為 O(n)付翁，其中 n 是節(jié)點(diǎn)的數(shù)量简肴。空間復(fù)雜度
空間復(fù)雜度： O(h)
棧的最大深度是樹的高度 h。在最壞的情況下（樹退化成鏈表）百侧，空間復(fù)雜度為 O(n)砰识。對于平衡二叉樹，空間復(fù)雜度為 O(log n)佣渴。
