题目描述
输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如,给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树:
3
/ \
9 20
/ \
15 7
限制:
0 <= 节点个数 <= 5000
算法1
利用前序遍历根节点是第一个
中序遍历是根节点分割左右子树元素为两边
C++ 代码
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder,
int prel, int prer, int inl, int inr)
{
//判断范围是否可行
if (prel > prer) return NULL;
int rootVal = preorder[prel];
TreeNode* root = new TreeNode(rootVal);
//在中序中寻找根节点 得到左子树和右子树的元素数目
int i = inl;
for (i = inl; i <= inr; i++) {
if (inorder[i] == rootVal) break;
}
int count = i - inl;
root->left = buildTree(preorder, inorder, prel + 1, prel + count, inl, inl + count - 1);
root->right = buildTree(preorder, inorder, prel + count + 1, prer, inl + count + 1, inr);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int r = inorder.size() - 1;
return buildTree(preorder, inorder, 0, r, 0, r);
}
};