力扣对应链接：105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）
牛客对应链接：重建二叉树_牛客题霸_牛客网 (nowcoder.com)
核心考点：二叉树重建，遍历理解，递归。
一、《剑指Offer》内容
二、分析问题
【经典二叉树问题】
根据 root 节点，将中序 vector 根据根节点划分为：左中序、右中序。
根据中序子序列长度，将前序 vector 划分为：根节点、左子树前序、右子树前序。
root->left 递归生成。
root->right 递归生成。
三、代码
//力扣AC的代码 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode* traversal(vector<int>& preorder, int pre_st, int pre_ed, vector<int>& inorder, int in_st, int in_ed) { if(pre_st>pre_ed || in_st>in_ed) return nullptr; TreeNode* root=new TreeNode(preorder[pre_st]); for(int i=0; i<inorder.size(); i++) { if(inorder[i]==preorder[pre_st]) { root->left=traversal(preorder, pre_st+1, (pre_st+1)+(i-in_st)-1, inorder, in_st, i-1); root->right=traversal(preorder, (pre_st+1)+(i-in_st-1)+1, pre_ed, inorder, i+1, in_ed); break; } } return root; } TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { int n=preorder.size(), m=inorder.size(); return traversal(preorder, 0, n-1, inorder, 0, m-1); } }; //力扣AC的代码（化简） /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode* traversal(vector<int>& preorder, int pre_st, int pre_ed, vector<int>& inorder, int in_st, int in_ed) { if(pre_st>pre_ed || in_st>in_ed) return nullptr; TreeNode* root=new TreeNode(preorder[pre_st]); for(int i=0; i<inorder.size(); i++) { if(inorder[i]==preorder[pre_st]) { root->left=traversal(preorder, pre_st+1, pre_st+i-in_st, inorder, in_st, i-1); root->right=traversal(preorder, pre_st+i-in_st+1, pre_ed, inorder, i+1, in_ed); break; } } return root; } TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { int n=preorder.size(), m=inorder.size(); return traversal(preorder, 0, n-1, inorder, 0, m-1); } }; //牛客AC的代码 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param preOrder int整型vector * @param vinOrder int整型vector * @return TreeNode类 */ TreeNode* traversal(vector<int>& preOrder, int pre_st, int pre_ed, vector<int>& vinOrder, int in_st, int in_ed) { if(pre_st>pre_ed || in_st>in_ed) return nullptr; TreeNode* root=new TreeNode(preOrder[pre_st]); for(int i=0; i<vinOrder.size(); i++) { if(vinOrder[i]==preOrder[pre_st]) { root->left=traversal(preOrder, pre_st+1, pre_st+i-in_st, vinOrder, in_st, i-1); root->right=traversal(preOrder, pre_st+i-in_st+1, pre_ed, vinOrder, i+1, in_ed); break; } } return root; } TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) { int n=preOrder.size(), m=vinOrder.size(); return traversal(preOrder, 0, n-1, vinOrder, 0, m-1); } };
四、细节处理
注意：这上面的代码采用的都是左闭右闭区间，所以在计算长度的时候要格外注意，建议通过画图来解决问题。
在递归左子树的参数中，前序遍历的终点值需要依靠中序遍历中根节点前面左中序的数量。而在递归右子树的参数中，前序遍历的起点值是左子树前序遍历终点值再 +1。
五、扩展
类似问题：106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode* traversal(vector<int>& inorder, int in_st, int in_ed, vector<int>& postorder, int post_st, int post_ed) { if(in_st>in_ed || post_st>post_ed) return nullptr; TreeNode* root=new TreeNode(postorder[post_ed]); for(int i=0; i<inorder.size(); i++) { if(inorder[i]==postorder[post_ed]) { root->left=traversal(inorder, in_st, i-1, postorder, post_st, post_st+(i-in_st)-1); root->right=traversal(inorder, i+1, in_ed, postorder, post_st+(i-in_st), post_ed-1); break; } } return root; } TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { int n=inorder.size(), m=postorder.size(); return traversal(inorder, 0, n-1, postorder, 0, m-1); } };
通过先序与后序遍历可以构造二叉树吗？
不一定可以。
为什么先序 + 后序不一定能推出二叉树？可参考以下例子：
在上图（1）（2）中，先序遍历的结果都是 AB，后序遍历的结果都是 BA，然而对应了两种结构，故无法判定；
但当先序序列是 ABC，后序序列是 BAC 时，唯一确定了图（3）。
