题目
给定一个树的前序遍历和中序遍历, 输出二叉树.
Input: preorder=[3,9,20,15,7], inorder=[9,3,15,20,7]
output:
3
/ \
9 20
/ \
15 7
思路1
递归, 通过为子树截取新的遍历数组, 空间复杂度过大.
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if (preorder.size() <= 0) return nullptr;
TreeNode* root = nullptr;
int val = preorder[0];
if (root == nullptr) {
root = new TreeNode(val);
};
vector<int>::iterator iter = find(inorder.begin(),inorder.end(), val);
int n = 0;
if (iter != inorder.end()){
// 迭代器位置
n = (int)distance(inorder.begin(),iter);
}
vector<int> leftInorder = vector<int>(inorder.begin(), inorder.begin() + n);
vector<int> rightInorder = vector<int>(inorder.begin() + n + 1, inorder.end());
vector<int> leftPreorder = vector<int>(preorder.begin() + 1, preorder.begin() + 1 + leftInorder.size());
vector<int> rightPreorder = vector<int>(preorder.begin() + 1 + leftInorder.size(), preorder.end());
root->left = buildTree(leftPreorder, leftInorder);
root->right = buildTree(rightPreorder, rightInorder);
return root;
}
思路2
递归, 计算出子节点的位置.
TreeNode* buildTreeRecrution (vector<int>& preorder, vector<int>& inorder, int left, int right, int &index) {
if (index >= preorder.size()) return nullptr;
while (left < right) {
if (preorder[index] == inorder[left]) break;
left++;
}
if (left >= right) return nullptr;
TreeNode *root = new TreeNode(preorder[index++]);
root->left = buildTreeRecrution(preorder, inorder, 0, left, index);
root->right = buildTreeRecrution(preorder, inorder, left + 1, right ,index);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int index = 0;
TreeNode* result = buildTreeRecrution(preorder, inorder, 0, (int)preorder.size(), index);
return result;
}
总结
关键是掌握前序和中序的关联, 分析数学问题, 找规律.
网友评论