144. Binary Tree Preorder Traversal

题干简述：

给我们一个二叉树的根节点，求该二叉树前序遍历结果。

解题思路

数据结构与算法课中必教的内容，前中后序遍历。使用 DFS 递归实现可以说是没有难度，重点就在于左右子树递归函数的执行位置与当前节点处理逻辑的相对位置关系。

BFS 要稍微复杂一点，通过一个数组模拟队列，但是这里我们不在使用 FIFO（先入先出），而是改为FILO（先入后出）的方式进行遍历，这样做的目的是为了确保节点处理的顺序是题干要求的前序遍历。

题解

/**
 * 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[]}
 */
// DFS 解法
var preorderTraversal = function(root) {
    const res = [];
    const dfs = (node) => {
        if (!node) return;
        res.push(node.val)
        dfs(node.left);
        dfs(node.right);
    }
    dfs(root);
    return res;
};

// BFS 解法
var preorderTraversal = function(root) {
    const res = [];
    const queue = [];
    queue.push(root);
    while (queue.length) {
        const node = queue.pop();
        if (!node) continue;
        res.push(node.val);
        queue.push(node.right);
        queue.push(node.left);
    }
    return res;
}

Q.E.D.

Take it easy