自顶向下递归,传递实参
思路
先解释一下create函数参数的含义:
preleft:代表当前子树在先序的开始下标;
preright:代表当前子树在先序的结束位置;
inleft:代表当前子树在中序的开始位置;
inright:代表当前子树在中序的结束位置;
注:不论在先序,中序,后序中,左子树元素或右子树元素总是挨在一块的;
首先前驱的第一个结点总是根结点;
然后根据这个根结点找到在中序中的对应位置,这样就可以确定左子树和右子树;
确定好左右子树后,继续递归即可;
代码
class Solution {
public:
void create(TreeNode*& p, int preleft, int preright, int inleft, int inright, vector<int>& preorder, vector<int>& inorder){
if(preleft > preright) return;
int idx = inleft;
for(; idx <= inright; idx++){
if(inorder[idx] == preorder[preleft]) break;
}
int num = idx - inleft;//左子树元素个数
p = new TreeNode(preorder[preleft]);
create(p->left, preleft + 1, preleft + num, inleft, idx-1, preorder, inorder);
create(p->right, preleft + num + 1, preright, idx + 1, inright, preorder, inorder);
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
TreeNode* root = NULL;
create(root, 0, preorder.size()-1, 0, inorder.size()-1, preorder, inorder);
return root;
}
};