144. 二叉树的前序遍历

[Geekhyt]

原题链接

前序遍历：先打印当前节点，再打印当前节点的左子树，最后打印当前节点的右子树 (ABCDEFG)

const preorderTraversal = function(root) {
    const result = [];
    function pushRoot(node){
        if (node !== null) {
            result.push(node.val);
            if (node.left !== null){ 
                pushRoot(node.left);
            }
            if (node.right !== null) {
                pushRoot(node.right);
            } 
        }
    }
    pushRoot(root);
    return result;
};

• 时间复杂度: O(n)
• 空间复杂度: O(n)

[yuetong3yu]

遍历实现

利用栈的特性

var preorderTraversal = function(root) {
    const ret = []
    if (!root) return ret
    const stack = [root]
    while(stack.length) {
        const cur = stack.pop()
        ret.push(cur.val)
        if (cur.left) stack.push(cur.left)
        if (cur.right) stack.push(cur.right)
    }
    return ret
};

二叉树后序遍历同理，中序遍历稍有不同。