144. Binary Tree Preorder Traversal

Leetcode

https://leetcode.com/problems/binary-tree-preorder-traversal/

題目

Given the root of a binary tree, return the preorder traversal of its nodes' values.

Example 1:

Input: root = [1,null,2,3]
Output: [1,2,3]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

解答

• 方法一

Recursion

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

Runtime: 118 ms, faster than 14.86% of JavaScript online submissions for Binary Tree Preorder Traversal.

Memory Usage: 42.2 MB, less than 37.80% of JavaScript online submissions for Binary Tree Preorder Traversal.

• 方法二

Iterations

利用 stack 紀錄遍歷所有節點

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

Runtime: 74 ms, faster than 71.22% of JavaScript online submissions for Binary Tree Preorder Traversal.

Memory Usage: 42.4 MB, less than 17.29% of JavaScript online submissions for Binary Tree Preorder Traversal.