144.二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

示例 1：

输入：root = [1,null,2,3]
输出：[1,2,3]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

提示：

• 树中节点数目在范围 [0, 100] 内
• -100 <= Node.val <= 100

进阶：递归算法很简单，你可以通过迭代算法完成吗？

思路：前序遍历：根节点-左节点-右节点

方法一：递归

 1 /**
 2  * Definition for a binary tree node.
 3  * function TreeNode(val, left, right) {
 4  *     this.val = (val===undefined ? 0 : val)
 5  *     this.left = (left===undefined ? null : left)
 6  *     this.right = (right===undefined ? null : right)
 7  * }
 8  */
 9 /**
10  * @param {TreeNode} root
11  * @return {number[]}
12  */
13 var preorderTraversal = function(root) {
14 let res =[];
15 if(root){
16     res.push(root.val);
17     res=res.concat(preorderTraversal(root.left));
18     res=res.concat(preorderTraversal(root.right));
19 }
20 return res;
21 };

复杂度分析：

• 时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次
• 空间复杂度：O(n)，为递归过程中栈的开销，平均情况下为 O(logn)，最坏情况下树呈现链状，为O(n)

 方法二：迭代

 1 /**
 2  * Definition for a binary tree node.
 3  * function TreeNode(val, left, right) {
 4  *     this.val = (val===undefined ? 0 : val)
 5  *     this.left = (left===undefined ? null : left)
 6  *     this.right = (right===undefined ? null : right)
 7  * }
 8  */
 9 /**
10  * @param {TreeNode} root
11  * @return {number[]}
12  */
13 var preorderTraversal = function(root) {
14     const res =[];
15     const stack = [];
16     while (root || stack.length){
17       while(root){
18         res.push(root.val);
19         stack.push(root);
20         root = root.left;
21       }
22       root = stack.pop();
23       root = root.right;
24     }
25     return res;
26 };

复杂度分析：

• 时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次
• 空间复杂度：O(n)，为递归过程中栈的开销，平均情况下为 O(logn)，最坏情况下树呈现链状，为O(n)