二叉树前序遍历算法实现

"二叉树的前序遍历是一种遍历或访问二叉树所有节点的方法，其中首先访问根节点，然后访问左子树，最后访问右子树。本资源提供了一个C++代码实现，用于解决给定一个二叉树根节点，返回其节点值的前序遍历数组。" 在计算机科学中，二叉树是一种数据结构，每个节点最多有两个子节点，通常分为左子节点和右子节点。前序遍历是二叉树遍历的一种常见方法，主要用于访问树中的所有节点。前序遍历的顺序是： 1. 访问根节点 2. 遍历左子树（如果存在） 3. 遍历右子树（如果存在） 对于给定的题目，目标是编写一个函数，接受一个二叉树的根节点，然后返回一个数组，包含按照前序遍历顺序访问的所有节点的值。 给出的C++代码实现中，定义了一个名为`Solution`的类，其中包含一个名为`preorderTraversal`的公共成员函数，该函数接收一个`TreeNode`类型的指针作为参数，表示二叉树的根节点。函数首先创建一个名为`res`的向量，用于存储前序遍历的结果。 在函数内部，使用两个指针`p1`和`p2`来遍历树。`p1`始终指向当前正在访问的节点，而`p2`用于帮助处理左子树的边界条件。当`p1`不为空时，函数执行以下操作： 1. 如果`p2`不为空且`p2->right`不为空，说明存在一个左子节点还没有被访问，因此将`p1`的值添加到结果向量`res`中，并更新`p2->right`为`p1`，以便于下次访问。 2. 如果`p2->right`为空，说明已经访问完左子树，将`p1`的值添加到`res`，然后更新`p1`为`p1->right`，继续访问右子树。 3. 如果`p1`为空，说明遍历完成，返回结果向量`res`。 这个算法使用了 Morris遍历方法，通过改变边界的链接来避免使用额外的栈或队列，从而在不牺牲空间效率的情况下进行前序遍历。这种方法对于理解和实现二叉树遍历很有帮助，因为它只需要常量级别的额外空间。 在给定的示例中，输入是一些特定形状的二叉树，输出是按照前序遍历顺序生成的节点值数组。例如，对于一个根节点为1，没有左子树，右子树为2,3的树，输出应为[1, 2, 3]。 总结来说，这个资源主要介绍了如何使用C++实现二叉树的前序遍历，通过Morris遍历方法有效地访问所有节点，而无需额外的数据结构。这对于理解和解决问题涉及到二叉树遍历的问题非常有帮助，同时也能加深对二叉树数据结构的理解。