二叉树的遍历

发表于 2024-04-04 更新于 2025-06-16 分类于数据结构阅读次数：

二叉树的知识每次用都要重新复习一遍，所以索性写一篇博客加强记忆

二叉树的遍历有四种方式：前序遍历、中序遍历、后续遍历、层序遍历，下面主要通过递归和显式栈的方式来实现前中后序遍历，层序遍历使用队列实现

前中后序遍历可以简便的记为： ‘中’的位置，即

前序遍历为：中左右

中序遍历为：左中右

后续遍历为：左右中

0.二叉树的定义

template<class T>
struct TreeNode{
   T val;
   TreeNode* left;
   TreeNode* right;
   TreeNode(T val): val(val), left(nullptr), right(nullptr);
};

1.前序遍历

前序遍历笼统来讲就是先访问根节点，再访问根节点的左子树，最后访问根节点的右子树

具体规则如下：

如果根节点为空，则返回

如果根节点不为空：

访问根节点

以前序遍历的方式访问左子树

以前序遍历的方式访问右子树

1.1 前序遍历的递归实现

步骤：

判断根结点是否为空，为空则返回
访问根节点
递归遍历左子树
递归遍历右子树

递归代码实现：

vector<int> res;
void preorder(TreeNode<int>* root) {
   if(!root) return;

   res.push_back(root->val);
   preorder(root->left);
   preorder(root->right);
}

时间复杂度分析：每个节点只会被访问一次，即O(n)，其中n是树中节点的数量

空间复杂度分析：递归的空间复杂度取决于树的高度，最坏情况下（完全不平衡的树）可以达到O(n)，其中n是树的节点数。对于平衡树，空间复杂度为O(log n)。

1.2 前序遍历的显式栈实现

显式栈即使用栈来模拟递归的过程

前序遍历的顺序为：根节点 - 左子树 - 右子树，根据栈的特点，入栈的顺序为: 右子树 - 左子树 - 根节点

步骤：

判断根节点时候为空，为空则返回
初始化维护一个栈，将根节点入栈
当栈不为空时：
1. 弹出并访问栈顶元素
2. 当node右子树不为空，将右子树入栈
3. 当node左子树不为空，将左子树入栈

显式栈的代码实现：

vector<int> preorder(TreeNode<int>* root) {
   vector<int> res;
   stack<TreeNode<int>*> st;
   st.push(root);
   
   while(st.size()) {
      TreeNode<int>* node = st.top();
      res.push_back(node->val);
      st.pop();

      if(node->right) st.push(node->right);
      if(node->left) st.push(node->left);
   }

   return res;
}

时间复杂度分析：与递归相同，每个节点只会被访问一次，即O(n)，其中n是树中节点的数量

空间复杂度分析：理论上与递归相同，但在实践中，因为手动管理栈，有时可以通过优化减少空间使用。

2. 中序遍历

中序遍历简单来说就是先访问根节点的左子树，再访问根节点，最后访问根节点的右子树

具体规则如下：

如果root为空则返回

如果root非空：

中序遍历根节点左子树

访问根节点

中序遍历根节点右子树

因为中序遍历的顺序是左中右，所以如果二叉树是搜索树，可以利用中序遍历来验证

2.1 中序遍历的递归实现

步骤：

判断根结点是否为空，为空则返回
递归遍历左子树
访问根节点
递归遍历右子树

递归代码实现：

vector<int> res;
void inorder(TreeNode<int>* root) {
   if(!root) return ;
   
   if(root->left) inorder(root->left);
   res.push_back(root->val);
   if(root->right) inorder(root->right);
}

时间复杂度分析： O(n)，同前序遍历

空间复杂度分析：同前序遍历

2.2 中序遍历的显式栈实现

因为是递归的显式栈实现，所以会比较难理解。

与前序遍历不同，访问根节点要放在左子树遍历完之后。因此我们需要保证：在左子树访问之前，当前节点不能提前出栈。

我们应该从根节点开始，循环遍历左子树，不断将当前子树的根节点放入栈中，直到当前节点无左子树时，从栈中弹出该节点并进行处理。

然后再访问该元素的右子树，并进行上述循环遍历左子树的操作。这样可以保证最终遍历顺序为中序遍历顺序。

二叉树的中序遍历显式栈实现步骤如下：

判断二叉树是否为空，为空则直接返回。
初始化维护一个空栈。
当根节点或者栈不为空时：
1. 如果当前节点不为空，则循环遍历左子树，并不断将当前子树的根节点入栈。
2. 如果当前节点为空，说明当前节点无左子树，则弹出栈顶元素node，并访问该元素，然后尝试访问该节点的右子树。

迭代代码实现：

vector<int> inorder(TreeNode<int>* root) {
   if(!root) return ;
   vector<int> res;

   stack<TreeNode<int>*> st;

   while(root || st.size()) {
      while(root) {
         st.push(root);
         root = root->left;
      }

      TreeNode<int>* node = st.top();
      st.pop();
      res.push_back(node->val);
      root = node->right;
   }
   
   return res;
}

3. 后序遍历

如果二叉树为空，则返回。

如果二叉树不为空，则：

以后序遍历的方式遍历根节点的左子树。

以后序遍历的方式遍历根节点的右子树。

访问根节点。

3.1 后序遍历递归实现

二叉树的后序遍历递归实现步骤为：

判断二叉树是否为空，为空则直接返回。
先递归遍历左子树。
然后递归遍历右子树。
最后访问根节点。

二叉树的后序遍历递归实现代码如下：

vector<int> res;
void postorder(TreeNode<int>* root) {
   if(!root) return;

   if(root->left) postorder(root->left);
   if(root->right) postorder(root->right);
   res.push_back(root->val);
}

3.2 后序遍历显式栈实现

不同于前两个遍历, 后续遍历需要保证: 再访问完根节点的左右两颗子树前, 不能访问根节点.

所以我们需要先遍历到最左边的节点, 然后访问判断其右子树是否存在或者已经访问过, 如果不存在或者访问过, 那么就访问根节点,否则访问右子树

vector<int> postorder(TreeNode<int>* root) {
   if(!root) return ;
   vector<int> res;
   stack<TreeNode<int>*> st;
   TreeNode<int>* prev;       

   while(root || st.size()) {
      while(root) {
         st.push(root);
         root = root->left;
      }

      TreeNode<int>* node = st.top();
      st.pop();

      if(!node->right || prev == node->right) {
         res.push_back(node->val);
         prev = node;
         root = nullptr;
      }
      else {
         st.push(node);
         root = node->right;
      }
   }
   return res;
   
}

4.层序遍历

层序遍历顾名思义，就是按照树的层数一层一层遍历，一般采用双向队列实现

层序遍历规则如下：

如果二叉树为空则返回

如果二叉树不为空:

访问第一层的节点

访问第二层的节点

…

访问最后一层的节点

4.1 层序遍历的队列实现

按照上面的规则我们很容易实现代码:

vector<vector<int>> levelorder(TreeNode<int>* root) {
   vector<vector<int>> res;
   if(!root) return res;

   queue<TreeNode<int>*> q;
   q.push(root);
   
   while(q.size()){
      int len = q.size();        // 队列保存当前层的节点, 所以len是当前层节点的数量
      vector<int> tmp;           // 存放当前层节点的值
      for(int i = 0; i < len; i++) {      // 只处理当前层的节点
         TreeNode<int>* node = q.front();    // 取出队头元素处理
         q.pop();                            // 删除队头元素
         tmp.push_back(node->val);           // 访问队头元素

         if(node->left) q.push(node->left);     // 如果左节点不为空, 把左节点入队
         if(node->right) q.push(node->right);
      }
      res.push_back(tmp);
   }


   return res;
}

参考资料

【文章】二叉树的遍历知识