二叉树先序遍历算法
在计算机科学中，二叉树是一种广泛应用的数据结构之一。它可以被认为是一种自然的树形结构，每个节点最多有两个子节点，称为左子树和右子树。而二叉树先序遍历算法则是一种遍历二叉树的方法，它可以先访问根节点，再访问左子树和右子树。
算法实现
二叉树先序遍历算法可以使用递归方法进行实现，也可以使用非递归方法进行实现。其中，递归实现方式相对较为简单，核心代码如下：
```c++
void preorder(TreeNode* root) {
if (root == nullptr) return;
cout << root->val << endl; // 访问当前节点
preorder(root->left); // 遍历左子树
preorder(root->right); // 遍历右子树
}
```
该算法的思路是，遍历二叉树的先序节点时，首先访问当前节点，然后再递归访问左子树和右子树。
而非递归实现方式则需要借助栈这一数据结构，核心代码如下：
```c++
void preorder(TreeNode* root) {
stack
if (root != nullptr) st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
st.pop();
cout << node->val << endl; // 访问当前节点
if (node->right != nullptr) st.push(node->right); // 将右子树入栈
if (node->left != nullptr) st.push(node->left); // 将左子树入栈
}
}
```
该算法的思路是，用栈来模拟递归的调用过程，将当前节点入栈。然后，不断从栈中取出节点，并访问它、将它的右子树和左子树依次入栈。
算法分析
二叉树先序遍历算法的时间复杂度为O(n)，其中n表示二叉树中节点的个数。对于每个节点而言，都需要进行一次访问操作，因此，时间复杂度与节点数成正比。同时，由于采用了递归或者栈来实现算法，因此在空间复杂度上也要额外开销O(h)，其中h表示二叉树的高度。
算法优化
虽然二叉树先序遍历算法已经达到了时间复杂度最优的状态，但在实际的应用场景中，还是可以做一定的优化。
一种常见的优化方式是，使用Morris方法。该方法不需要额外的栈空间，仅通过利用二叉树中空闲的指针，将算法的空间复杂度降低至O(1)。其核心思路是，一旦没有左子树时，输出当前节点，并将节点指向右子树。如果有左子树，则在左子树中找到当前节点在中序遍历下的前驱节点，并将其后继指向当前节点。具体实现详见以下代码。
```c++
void preorder(TreeNode* root) {
TreeNode* cur = root;
while (cur) {
if (cur->left) {
TreeNode* predecessor = cur->left;
while (predecessor->right && predecessor->right != cur) {
predecessor = predecessor->right;
}
if (!predecessor->right) {
cout << cur->val << endl; // 访问当前节点
predecessor->right = cur; // 将当前节点作为前驱节点的后继
cur = cur->left; // 遍历左子树
} else {
predecessor->right = nullptr;
cur = cur->right; // 遍历右子树
}
} else {
cout << cur->val << endl; // 访问当前节点
cur = cur->right; // 遍历右子树
}
}
}
```
算法
