问题描述
给定一颗二叉树，以先序遍历的顺序返回其节点。
栗子：
输入：[1,null,2,3]
1
\
2
/
3
输出：[1,2,3]
最后，题主还附加了一句：使用递归没啥，你能够用遍历的方式完成吗？
解题思路
首先，介绍一下先序遍历。
始终是先遍历根节点，再遍历左节点，最后遍历右节点。对于子树也一样。
递归
使用递归的方式是最简单的，按根节点 -> 左节点 -> 右节点的顺序即可。
由于题目要求返回遍历的节点，因此将节点存入数组就好。
直接上代码：
var preorderTraversal = function (root) {
let result = [];
preoderTraversalRecursive(root, result);
return result;
};
var preoderTraversalRecursive = function (root, result) {
if (root) {
// 根节点
result.push(root.val);
// 左节点
preoderTraversalRecursive(root.left, result);
// 右节点
preoderTraversalRecursive(root.right, result);
}
};
遍历
如果以遍历的方式，稍微复杂一丢丢，但是实现起来也不困难。
主要是利用栈的思想，先进后出。由于左节点要先于右节点遍历，因此将右节点先进栈，左节点后进栈。
该实现的 js 代码如下：
var preoderTraversalIterative = function (root) {
let result = [];
if (root) {
let list = [];
list.push(root);
while (list.length > 0) {
// 取第一个数据
const node = list.shift();
result.push(node.val);
// 右节点进栈
if (node.right) {
list.unshift(node.right);
}
// 左节点进栈
if (node.left) {
list.unshift(node.left);
}
}
}
return result;
};
