对二叉树进行前序遍历
二叉树是一种常见的树形数据结构。在二叉树中，每个节点有两个分支，分别称为左子树和右子树。前序遍历是一种递归遍历算法，它将二叉树以根节点、左子树、右子树的方式遍历一遍。本文将从多个角度介绍二叉树前序遍历算法。
递归算法
二叉树前序遍历算法最常见的实现方式是递归算法。递归算法是指在函数内部调用自身的算法。在对二叉树进行前序遍历时，首先访问当前节点，然后递归地访问左子树，最后递归地访问右子树。以下是对应的代码：
```
void preorderTraversal(TreeNode* root) {
if (root == NULL) return;
visit(root);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
```
其中，visit(root)是对访问当前节点的操作。在这里，我们可以输出节点的值，或者将节点插入到一个数组中。如果当前节点为NULL，则直接返回。
栈算法
另一个实现二叉树前序遍历的方法是使用栈。栈是一种后进先出（LIFO）的数据结构，我们可以用栈来实现前序遍历算法的非递归版本。在对二叉树进行前序遍历时，我们首先将根节点压入栈中，然后按照根节点、右子树、左子树的顺序依次将节点压入栈中。以下是对应的代码：
```
void preorderTraversal(TreeNode* root) {
if (root == NULL) return;
stack
s.push(root);
while (!s.empty()) {
TreeNode* node = s.top();
s.pop();
visit(node);
if (node->right != NULL) s.push(node->right);
if (node->left != NULL) s.push(node->left);
}
}
```
其中，visit(node)是对访问当前节点的操作。在这里，我们可以输出节点的值，或者将节点插入到一个数组中。如果栈不为空，则从栈中弹出一个节点，并按照右子树、左子树的顺序将其非空子节点压入栈中。
Morris算法
Morris算法是一种空间复杂度为O(1)的二叉树遍历算法，它可以实现前序遍历、中序遍历和后序遍历。Morris算法的核心思想是将当前处理的节点的左子树的最右节点（也就是左子树的最大值）与该节点连接起来，使得每个节点最多只需访问两次即可。以下是对应的代码：
```
void preorderTraversal(TreeNode* root) {
if (root == NULL) return;
TreeNode* node = root;
while (node != NULL) {
if (node->left == NULL) {
visit(node);
node = node->right;
} else {
TreeNode* pre = node->left;
while (pre->right != NULL && pre->right != node) {
pre = pre->right;
}
if (pre->right == NULL) {
visit(node);
pre->right = node;
node = node->left;
} else {
pre->right = NULL;
node = node->right;
}
}
}
}
```
其中，visit(node)是对访问当前节点的操作。在这里，我们可以输出节点的值，或者将节点插入到一个数组中。如果当前节点的左子树为空，则访问当前节点，并将指针移动到右子树。否则，找到左子树的最右节点，并将该节点的right指针指向当前节点。如果左子树的最右节点已经指向了当前节点，则访问当前节点，并将该节点的right指针置为NULL，然后将指针移动到右子树。
