二叉树的遍历

二叉树的常见遍历方式分类：

• 深度优先遍历

  • 前序遍历（根 -> 左 -> 右）

  • 中序遍历（左 -> 根 -> 右）

  • 后序遍历（左 -> 右 -> 根）

• 广度优先遍历

  • 层序遍历

前序遍历（Pre-Order）

简单来说，就是根节点 -> 左子树 -> 右子树

递归实现

void preorderRecursive(TreeNode* node, vector<int>& res) {
    if (!node) return;                  // 1. 访问根节点
    res.push_back(node->val);
    preorderRecursive(node->left, res); // 2. 遍历左子树
    preorderRecursive(node->right, res);// 3. 遍历右子树
}

迭代实现（借助栈实现）

vector<int> preorderIterative(TreeNode* root) {
    vector<int> res;
    if (!root) return res;
    stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        TreeNode* node = st.top(); st.pop();
        res.push_back(node->val);       		// 访问当前节点
        if (node->right) st.push(node->right); 	// 右子树后入栈
        if (node->left)  st.push(node->left);  	// 左子树先入栈
    }
    return res;
}

注意，因为队列先进先出的特性，不可以用来设计并完成对二叉树的深度优先遍历，因为它无法对子树进行递归深入，而只有栈可以完成对应的操作；

中序遍历（In-Order）

简单来说，就是左子树 -> 根节点 -> 右子树

对于一个二叉搜索树来说，中序遍历的结果是一个有序数组（升序）

递归实现

void inorderRecursive(TreeNode* node, vector<int>& res) {
    if (!node) return;                  
    inorderRecursive(node->left, res);  // 1. 遍历左子树
    res.push_back(node->val);           // 2. 访问根节点
    inorderRecursive(node->right, res); // 3. 遍历右子树
}

迭代实现（借助栈）

vector<int> inorderIterative(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> st;
    TreeNode* curr = root;
    while (curr || !st.empty()) {
        // 一直沿左子树压栈
        while (curr) {
            st.push(curr);
            curr = curr->left;
        }
        // 访问节点并转向右子树
        curr = st.top(); st.pop();
        // 对根节点的访问
        res.push_back(curr->val);
        curr = curr->right;
    }
    return res;
}

后序遍历（Post-Order）

简单来说，就是左子树 -> 右子树 -> 根节点

递归实现

void inorderRecursive(TreeNode* node, vector<int>& res) {
    if (!node) return;                  
    inorderRecursive(node->left, res);  // 1. 遍历左子树
    inorderRecursive(node->right, res); // 3. 遍历右子树
    res.push_back(node->val);
}

迭代实现（双栈或单栈技巧）

• 双栈法

  vector<int> postorderIterative(TreeNode* root) {
      vector<int> res;
      if (!root) return res;
      stack<TreeNode*> st1, st2;
      st1.push(root);
      while (!st1.empty()) {
          TreeNode* node = st1.top(); st1.pop();
          st2.push(node);
          // 注意栈FILO特性
          if (node->left)  st1.push(node->left);
          if (node->right) st1.push(node->right);
      }
      // st2 中存储的是根→右→左，弹出即左→右→根
      while (!st2.empty()) {
          res.push_back(st2.top()->val);
          st2.pop();
      }
      return res;
  }

• 单栈法（标记法/跟踪上次访问节点）

  // 需要保证在访问根节点时左右子树都已经被访问过
  // 借助额外的lastVisited指针记录上一次访问的节点
  vector<int> postorderIterativeOneStack(TreeNode* root) {
      vector<int> res;
      stack<TreeNode*> st;
      TreeNode* lastVisited = nullptr;
      TreeNode* curr = root;
      while (curr || !st.empty()) {
          while (curr) {
              st.push(curr);
              curr = curr->left;
          }
          TreeNode* peekNode = st.top();
          // 如果右子树不存在或已访问，则访问当前
          if (!peekNode->right || peekNode->right == lastVisited) {
              res.push_back(peekNode->val);
              lastVisited = peekNode;
              st.pop();
          } else {
              curr = peekNode->right;
          }
      }
      return res;
  }

层序遍历（Level-Order）

这是广度优先遍历的应用，需要通过队列模拟实现

迭代实现

vector<int> levelorderIterative(TreeNode* root){
    vector<int> res;
    if(root == nullptr) return res;
    queue<TreeNode*> que;
    que.push(root);
    
    // size 表示每一层的大小
    while(!que.empty()){
		int size = que.size();
        for(int i = 0; i < size; ++i){
            // size 表示的就是每一层的元素数量
            TreeNode* top = que.front(); que.pop();
            res.push_back(top->val);
            if(top->left) que.push(top->left);
            if(top->right) que.push(top->right);
        }
    }
    return res;
}

递归实现（基于深度／层数）

// 通过引入depth变量
// 对每次遍历的结果进行分层
// 从而通过递归实现层序遍历
void dfsLevel(TreeNode* node, int depth, vector<vector<int>>& res) {
    if (!node) return;
    if (depth == res.size())
        res.push_back({});            		// 新层时创建新子数组
    res[depth].push_back(node->val);
    dfsLevel(node->left,  depth+1, res);	// 访问对应深度的左子树, 深度递增
    dfsLevel(node->right, depth+1, res);	// 访问对应深度的右子树, 深度递增
}

vector<vector<int>> levelOrderRecursive(TreeNode* root) {
    vector<vector<int>> res;
    dfsLevel(root, 0, res);
    return res;
}