算法1
(递归) $时间O(n),空间O(log(n))$
用迭代器查找(也可以用散列保存 节点值 对应的 中序序列索引)。
C++ 代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int n;
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
n = preorder.size();
return help(0, n - 1, 0, n - 1, preorder, inorder);
}
TreeNode* help(int pl, int pr, int il, int ir, vector<int>& preorder, vector<int>& inorder) {
if(pl > pr) return NULL;
TreeNode* res = new TreeNode(preorder[pl]);
int x = find(begin(inorder), end(inorder), preorder[pl]) - begin(inorder);
if(x == n) return res;
res->left = help(pl + 1, pl + x - il, il, x - 1, preorder, inorder);
res->right = help(pl + x - il + 1, pr, x + 1, ir, preorder, inorder);
return res;
}
};