本文共 2648 字，大约阅读时间需要 8 分钟。

经典二叉树遍历问题仅指我个人的定义

1. 第1类(给遍历，构造树)

构造二叉树的方法主要有三种：从前序与中序遍历、从中序与后序遍历以及从中序与层序遍历。

(1) 从前序与中序遍历构造二叉树

这一问题对应于LeetCode 105，可以通过递归找出根节点在中序遍历中的位置，并将中序遍历中 interleaving 分割为左右子树的中序遍历和前序遍历。这一实现方式代码量较少，但在性能上有一定限制。

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {   public:    TreeNode* buildTree(vector
   
    & preorder, vector
    
     & inorder) {        if (preorder.empty()) return NULL;        TreeNode* root = new TreeNode(preorder[0]);        auto it = lower_bound(inorder.begin(), inorder.end(), preorder[0]);        vector
     
       leftPreorder(preorder.begin()+1, preorder.begin()+1+it-inorder.begin()),            rightPreorder(preorder.begin()+it-inorder.begin()+1, preorder.end());        vector
      
        leftInorder(inorder.begin(), it), rightInorder(it, inorder.end());        root->left = buildTree(leftPreorder, leftInorder);        root->right = buildTree(rightPreorder, rightInorder);        return root;    }}
      
     
    
   

(2) 从中序与后序遍历构造二叉树

这一问题对应于LeetCode 106。根节点可以通过后序遍历的最后一个元素在中序遍历中的位置确定，同样利用分弦法分割左右子树的后序遍历和中序遍历。

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {   public:    TreeNode* myBuildTree(const vector
   
    & inorder, int headI, int tailI, const vector
    
     & postorder, int headP, int tailP) {        if (headI > tailI) return NULL;        TreeNode* root = new TreeNode(postorder[tailP]);        for (int i = headI; i <= tailI; ++i) {            if (inorder[i] == postorder[tailP]) {                break;            }        }        int mid = i;        root->left = myBuildTree(inorder, headI, mid-1, postorder, headP, headP + (mid - headI - 1));        root->right = myBuildTree(inorder, mid+1, tailI, postorder, headP + (mid - headI), tailP-1);        return root;    }    TreeNode* buildTree(const vector
     
      & inorder, const vector
      
       & postorder) {        if (inorder.empty()) return NULL;        return myBuildTree(inorder, 0, inorder.size()-1, postorder, 0, postorder.size()-1);    }}
      
     
    
   

(3) 从中序与层序遍历构造二叉树

这一问题结合了中序遍历和层序遍历的信息，需要先确定根节点在层序遍历中的位置，然后通过中序遍历分割左右子树的层序遍历。

2. 第2类(给遍历，求遍历)

通过给定的两种遍历，可以求得第三种遍历的结果。

(1) 中序遍历 + 前序遍历 -> 后序遍历

可以通过递归访问右子树和左子树，再将前序遍历结果转换为后序遍历。

(2) 中序遍历 + 后序遍历 -> 前序遍历

可递归地访问左子树和右子树，并将后序遍历结果转换为前序遍历。

(3) 中序遍历 + 层序遍历 -> 前序遍历

需要通过层序遍历信息和中序遍历信息构造出前序遍历的结果，具体步骤为确定根节点，并按层序和中序信息分割左右子树。

3. 总结

这一系列问题的核心在于如何将多种遍历形式有效地结合起来，通过递归分割和构造的方法，能够实现二叉树的构造和遍历转换。