105. 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。 注意:你可以假设树中没有重复的元素。 例如，给出 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树： 3 / \ 9 20 / \ 15 7

解题思路

前序遍历
整体思路：划分中序遍历为 左子树 根 右子树 ，然后递归划分
具体地：
image.png
把前序遍历数组中的每个值作为一个子树的root，对于前序遍历数组中任意一个root，到中序遍历中寻找此root，根据root的位置，将原中序遍历数组划分为3段， [ ``inL``, inRootIndex -1 ] root [ inRootIndex + 1,``inR``]
而此时左子树的结点个数为 leftNums = inRootIndex - inL，

  • [ inL, inRootIndex -1 ] 部分作为此 root 的左子树的中序遍历， 其根的范围在前序遍历中变为 [ preL+ 1,preL + leftNums ]
  • [ inRootIndex +1,inR] 部分作为此root的左子树的中序遍历，其根的范围在前序遍历中变为[ preL+leftNums+1,preR ]

递归终止的条件就是中序数组或者前序数组之间没有元素，即 (preL > preR || inL > inR ) ，此时当前结点就是NULL，返回上层就会作为空的左孩子或者右孩子

  1. class Solution {
  2. public:
  3.     TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
  4.         TreeNode* root = bulld(0,preorder.size()-1,0,inorder.size()-1,preorder,inorder);
  5.         return root;
  6.     }
  7.     /*左闭右闭区间，preorder[preR->preL],inorder[inR->inL]
  8.       根据前序遍历的第一个元素在中序遍历中找到其位置，将中序遍历划分为此结点的左右子树区间，
  9.       分别作为此结点的左右子树
  10.     */
  11.     TreeNode* bulld(int preL,int preR,int inL,int inR,vector<int>& preorder, vector<int>& inorder){
  12.         if(preL > preR || inL > inR){
  13.             return NULL;
  14.         }
  15.         TreeNode* root = new TreeNode(preorder[preL]);
  16.         vector<int>::iterator it = find(inorder.begin(),inorder.end(),root->val);
  17.         int inRootIndex = &*it-&inorder[0];
  18.         int leftNums = inRootIndex - inL;
  19.         root->left = bulld(preL+1,preL+leftNums,inL,inRootIndex -1,preorder,inorder);
  20.         root->right = bulld(preL+leftNums+1,preR,inRootIndex+1,inR,preorder,inorder);
  21.         return root;
  22.     }
  23. };