144. Binary Tree Preorder Traver

递归解法

• Runtime: 76 ms, faster than 63.69%
• Memory Usage: 36.2 MB, less than 57.73%

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
    if (!root) return []
    let res = []
    
    let recursive = function(node){
        res.push(node.val)
        if(node.left) recursive(node.left)
        if(node.right) recursive(node.right)
    }
    recursive(root)
    return res
};

非递归解法

• Runtime: 72 ms, faster than 78.37%
• Memory Usage: 37.1 MB, less than 6.96%

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
    if(!root) return []
    let res = []
    let stack = []
    let p = root
    while(stack.length !== 0 || p !== null) {
        if(p !== null) {
            stack.push(p)
            res.push(p.val)
            p = p.left
        } else {
            let node = stack.pop()
            p = node.right
        }
    }
    return res
};

更容易理解的非递归实现

• Runtime: 72 ms, faster than 78.37%
• Memory Usage: 36.9 MB, less than 21.42%

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
    if(!root) return []
    let stack = [root]
    let res = []
    while(stack.length > 0) {
        const { val, left, right } = stack.pop()
        if (right) stack.push(right)
        if (left) stack.push(left)
        res.push(val)
    }
    return res
};

一行实现

• Runtime: 80 ms, faster than 45.89%
• Memory Usage: 37.4 MB, less than 5.04%

const preorderTraversal = (root) => root ? [root.val, ...preorderTraversal(root.left), ...preorderTraversal(root.right)] : []