Construct Binary Tree from Preorder and Inorder Traversal.png
解題思路 ：
利用 preorder 的頭找到 root 的值 再用 root 值去 inorder 找到 root 在 inorder 中的 index 接著用 inorder 的頭到 index -1 的範圍當作左子數的範圍 index + 1 到 index 尾的範圍當右邊子樹的範圍繼續 recursive
C++ code :
<pre><code>
/**
- Definition of TreeNode:
- class TreeNode {
- public:
int val;TreeNode *left, *right;TreeNode(int val) {this->val = val;this->left = this->right = NULL;}- }
*/
class Solution {
/**
*@param preorder : A list of integers that preorder traversal of a tree
*@param inorder : A list of integers that inorder traversal of a tree
*@return : Root of a tree
*/
public:
int getIndex(vector<int> &v, int value)
{
for(int i = 0; i < v.size(); i++)
{
if(v[i] == value) return i;
}
return -1;
}
TreeNode *construct(vector<int> &pre, int Pstart, int Pend, vector<int> &in, int Istart, int Iend)
{
if (Pstart > Pend) return nullptr;
int root_val = pre[Pstart];
int index = getIndex(in, root_val);
TreeNode *root = new TreeNode(root_val);
root->left = construct(pre, Pstart + 1, Pstart + (index - Istart), in, Istart, index - 1);
root->right = construct(pre, Pstart + (index - Istart) + 1, Pend, in, index + 1, Iend);
return root;
}
TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
// write your code here
int Pend = preorder.size() - 1;
int Iend = inorder.size() - 1;
return construct(preorder, 0, Pend, inorder, 0, Iend);
}
};
