Problem: 105. 从前序与中序遍历序列构造二叉树
首先明确:
1.前序遍历的顺序是根-左-右(即先遍历根节点,再左子树,再右子树)
2.中序遍历的顺序是左-右-根
1.前序遍历数组中的第一个元素一定是树的根节点
2.每次在前序数组中找出根节点,再到的中序数组中找出根节点,则在中序数组中该根节点的左侧为根节点的左子树、右侧是根节点的右子树(则我们每次要重复该操作去构造二叉树)
1.定义构造二叉树的递归函数TreeNode* build(vector& preorder, int preStart, int preEnd, vector& inorder, int inStart, int inEnd)其中preStart是每次递归前序遍历数组中的起始位置preEnd是每次递归前序遍历数组中的结束位置,同理inStart 每次递归中序遍历数组的起始位置inEnd每次递归数组的结束位置
2.定义一个unordered_mapvalToIndex;在中序遍历数组中每次根节点的索引位置 再再中序数组中找出当前父节点的索引(index),通过计算得到左子树所有节点的长度:int leftSize = index - inStart;
3.每次递归中先在先序数组中取出当前的父节点
4.下一次递归的起始与结束位置为preStart + 1, preStart + leftSize,inStart, index - 1,preStart + leftSize + 1,index + 1, inEnd
时间复杂度:
O ( n ) O(n) O(n);其中 n n n为树节点的个数
空间复杂度:
O ( h e i g h ) O(heigh) O(heigh);其中 h e i g h t height height为树的高度
/**
* 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 {
//Recode the element of inorder array into the unorderd_map
unordered_map<int, int>valToIndex;
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
for (int i = 0; i < inorder.size(); ++i) {
valToIndex[inorder[i]] = i;
}
return build(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
}
TreeNode* build(vector<int>& preorder, int preStart, int preEnd, vector<int>& inorder, int inStart, int inEnd) {
//Base case
if (preStart > preEnd) {
return nullptr;
}
//The first element in preorder array is the root of binary tree that
//we shoud creat
int rootVal = preorder[preStart];
//Find the index of rootVal in inorder array
int index = valToIndex[rootVal];
//Calculate the size of left tree
int leftSize = index - inStart;
//Create the root firstly
TreeNode* root = new TreeNode(rootVal);
// Recursively construct the left and right subtrees
root -> left = build(preorder, preStart + 1, preStart + leftSize, inorder, inStart, index - 1);
root -> right = build(preorder, preStart + leftSize + 1, preEnd, inorder, index + 1, inEnd);
return root;
}
};