对二叉树进行前序遍历

二叉树是一种常见的树形数据结构。在二叉树中，每个节点有两个分支，分别称为左子树和右子树。前序遍历是一种递归遍历算法，它将二叉树以根节点、左子树、右子树的方式遍历一遍。本文将从多个角度介绍二叉树前序遍历算法。

递归算法

二叉树前序遍历算法最常见的实现方式是递归算法。递归算法是指在函数内部调用自身的算法。在对二叉树进行前序遍历时，首先访问当前节点，然后递归地访问左子树，最后递归地访问右子树。以下是对应的代码：

```

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;

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，然后将指针移动到右子树。