day18 二叉树遍历总结
二叉树遍历总结
遍历二叉树是指按照一定的顺序遍历二叉树中的每个节点。常见的遍历方式有前序遍历、中序遍历和后序遍历。以下是它们的具体实现：
-
前序遍历：按照“根节点-左子树-右子树”的顺序进行遍历。具体实现的步骤如下：
- 访问根节点
- 对根节点的左子树进行前序遍历
- 对根节点的右子树进行前序遍历
前序遍历的递归实现代码如下：
void preorder(TreeNode* root) { if (root == nullptr) return; visit(root); preorder(root->left); preorder(root->right); } -
中序遍历：按照“左子树-根节点-右子树”的顺序进行遍历。具体实现的步骤如下：
- 对根节点的左子树进行中序遍历
- 访问根节点
- 对根节点的右子树进行中序遍历
中序遍历的递归实现代码如下：
void inorder(TreeNode* root) { if (root == nullptr) return; inorder(root->left); visit(root); inorder(root->right); } -
后序遍历：按照“左子树-右子树-根节点”的顺序进行遍历。具体实现的步骤如下：
- 对根节点的左子树进行后序遍历
- 对根节点的右子树进行后序遍历
- 访问根节点
后序遍历的递归实现代码如下：
void postorder(TreeNode* root) { if (root == nullptr) return; postorder(root->left); postorder(root->right); visit(root); }
以上是二叉树的三种遍历方式的递归实现。当然，这些方法也可以通过非递归的方式实现，例如使用栈来模拟遍历过程。