二叉树的先序遍历

先序遍历（Preorder Traversal）是指先将根节点输出，再依次遍历左右子树的过程。在二叉树中，它是最自然也是最常用的遍历方式之一。下面从多个角度对先序遍历进行分析。

1. 实现方法

先序遍历可以使用递归或者非递归的方式来实现。递归方式的代码如下：

```

void preOrderTraversal(TreeNode* root) {

if (root == NULL) return;

cout << root->val << " ";

preOrderTraversal(root->left);

preOrderTraversal(root->right);

}

```

非递归方式的代码如下：

```

void preOrderTraversal(TreeNode* root) {

stack s;

TreeNode* current = root;

while (!s.empty() || current != NULL) {

if (current != NULL) {

cout << current->val << " ";

s.push(current);

current = current->left;

} else {

current = s.top();

s.pop();

current = current->right;

}

}

}

```

2. 应用场景

先序遍历的应用非常广泛，例如基于二叉树的算法中很多问题都可以使用先序遍历来解决，比如计算二叉树的深度、判断两个二叉树是否相等等。此外，在图像处理中也可以使用先序遍历的思想来处理像素点的颜色信息，从而实现图像的变换和特效的实现。

3. 时间复杂度

对于一棵有n个节点的二叉树，先序遍历需要遍历每个节点恰好一次，因此时间复杂度为O(n)。

4. 空间复杂度

递归方式的先序遍历需要根据递归深度消耗O(h)的栈空间，其中h为二叉树的高度。而非递归方式的先序遍历需要使用一个栈来辅助遍历，因此空间复杂度也是O(h)。