LeetCode105. Construct Binary Tree from Preorder and Inorder Traversal

一、题目

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Example 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
Example 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

Constraints:

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder and inorder consist of unique values.
Each value of inorder also appears in preorder.
preorder is guaranteed to be the preorder traversal of the tree.
inorder is guaranteed to be the inorder traversal of the tree.

二、题解

利用preorder.assign(preorder.begin()+1,preorder.end());对原有的前序数组进行切片（弹出第一个元素），类似106题中将后序数组进行resize

/*** 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* buildTree(vector<int>& preorder, vector<int>& inorder) {if(preorder.size() == 0) return nullptr;int rootVal = preorder[0];TreeNode* root = new TreeNode(rootVal);if(preorder.size() == 1) return root;//切分中序数组vector<int> leInorder;vector<int> riInorder;int index = 0;for(int i = 0;i < inorder.size();i++){if(inorder[i] == rootVal){index = i;break;}}for(int i = 0;i < index;i++) leInorder.push_back(inorder[i]);for(int i = index + 1;i < inorder.size();i++) riInorder.push_back(inorder[i]);//重置前序数组preorder.assign(preorder.begin()+1,preorder.end());//切分前序数组vector<int> lePreorder;vector<int> riPreorder;for(int i = 0;i < leInorder.size();i++) lePreorder.push_back(preorder[i]);for(int i = leInorder.size();i < preorder.size();i++) riPreorder.push_back(preorder[i]);root->left = buildTree(lePreorder,leInorder);root->right = buildTree(riPreorder,riInorder);return root;}
};