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)。