前序遍历

前序遍历（Pre-Order Traversal）首先操作根节点，然后操作左子树，再操作右子树；在遍历左右子树时，仍然是先操作根节点，然后操作左子树、再操作右子树

算法

递归

const preOrderTraversal = (root) => {
	if (!root) return [];
	const res = [];
	const preOrderRecursion = (node) => {
		res.push(node.val);
		if (node.left) preOrderRecursion(node.left);
		if (node.right) preOrderRecursion(node.right);
	};
	preOrderRecursion(root);
	return res;
};

迭代一

我们使用栈stack来存储待遍历的节点：每次弹出栈顶的元素作为根节点进行操作，如果根节点存在右孩子，在栈中压入右孩子；然后判断根节点是否有左孩子，如果有则压入左孩子；然后我们继续弹出栈顶元素作为新的根节点继续操作...直到栈为空

const preOrderTraversal = (root) => {
	if (!root) return [];
	const res = [];
	const stack = [root];
	while (stack.length) {
		const node = stack.pop();
		res.push(node.val);
		if (node.right) stack.push(node.right);
		if (node.left) stack.push(node.left);
	}
	return res;
};

迭代二

先遍历左节点，直到没有左节点后我们回溯到父节点，然后继续遍历左节点...

使用栈stack来保存每一个还没有操作右孩子的节点

只要节点存在，我们就将其值推入结果数组，然后将它压入栈stack表示这个节点的已经操作但是这个节点的右孩子还没有操作，然后我们将这个节点的左孩子当作新的节点重复上面的操作，直到这个节点没有左孩子；然后我们弹出栈顶节点（也就是当前没有左孩子的节点的父节点），将这个节点的右孩子作为新的节点重复之前的操作

const preOrderTraversal = (root) => {
	if (!root) return [];
	const res = [];
	const stack = [];
	while (root || stack.length) {
		if (root) {
			stack.push(root);
			res.push(root.val);
			root = root.left;
		} else {
			root = stack.pop();
			root = root.right;
		}
	}
	return res;
};