題目鏈接
https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
代碼
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int pi = 0;
return dfs(preorder, pi, inorder, 0, inorder.size() - 1);
}
TreeNode* dfs(vector<int>& preorder, int &pi, vector<int>& inorder, int is, int it) {
if (is > it) {
return NULL;
}
int val = preorder[pi];
TreeNode *parent = new TreeNode(val);
int pos = is;
while (pos <= it && val != inorder[pos]) {
pos++;
}
pi++;
parent->left = dfs(preorder, pi, inorder, is, pos - 1);
parent->right = dfs(preorder, pi, inorder, pos + 1, it);
return parent;
}
};
