AcWing 18. 重建二叉树
原题链接
中等
作者:
wjie
,
2020-07-16 23:35:47
,
所有人可见
,
阅读 494
class Solution {
public:
TreeNode* dfs(vector<int>& preorder, vector<int>& inorder, int pl, int pr, int il, int ir)
{
TreeNode* res = new TreeNode(preorder[pl]);
if (pr == pl) return res;
int idx = il;
while (inorder[idx] != preorder[pl]) ++idx;
int lengths = idx - il;
if (idx > il)
res->left = dfs(preorder, inorder, pl+1, pl+1+lengths-1, il, idx-1);
if (idx < ir)
res->right = dfs(preorder, inorder, pl+lengths+1, pr, idx+1, ir);
return res;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if (preorder.empty()) return NULL;
return dfs(preorder, inorder, 0, preorder.size()-1, 0, inorder.size()-1);
}
};