题目：
给定一个二叉树，返回它的 前序 遍历。
示例:
输入: [1,null,2,3]
1
\
3
/
2
输出: [1,2,3]
方法一 递归
思路：
先序遍历二叉树的操作定义
1、访问根结点
2、先序遍历左子树
3、先序遍历右子树
时间复杂度:O(n)
空间复杂度:最坏情况下需要空间O(n)O(n)，平均情况为O(logn)
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var preorderTraversal = function(root) {
let res = [];
helper(root,res);
return res;
};
var helper = function(root, res) {
if(root){
res.push(root.val);
helper(root.left, res);
helper(root.right, res);
}
};
方法二 迭代
思路：
1、从根节点开始，每次迭代弹出当前栈顶元素，并将其孩子节点压入栈中，先压右孩子再压左孩子。
2、在这个算法中，输出到最终结果的顺序按照 Top->Bottom 和 Left->Right，符合前序遍历的顺序。
时间复杂度:O(n)
空间复杂度:O(n)
var preorderTraversal = function(root) {
let res = [], stack = [];
if(!root) return [];
stack.push(root);
while(stack.length){
let p = stack.pop();
res.push(p.val);
if(p.right){
stack.push(p.right)
}
if(p.left){
stack.push(p.left)
}
}
return res;
};
