地址 https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
解答
同106 和剑指Offer 007. 重建二叉树 递归 类似
利用前序遍历根节点是第一个
中序遍历是根节点分割左右子树元素为两边 逐步分解问题到子问题
class Solution {
public:
TreeNode* dfs(vector<int>& preorder, int pl, int pr, vector<int>& inorder, int il, int ir) {
if (pr < pl) return NULL;
int rootval = preorder[pl];
int rootIdx = il;
for (rootIdx = il; rootIdx <= ir; rootIdx++) {
if (inorder[rootIdx] == rootval) { break; }
}
TreeNode* p = new TreeNode(rootval);
int inleft = rootIdx - il;
int inright = ir - rootIdx;
p->left = dfs(preorder, pl + 1, pl + inleft, inorder, il, il + inleft - 1);
p->right = dfs(preorder, pr - inright + 1, pr, inorder, ir - inright + 1, ir);
return p;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return dfs(preorder, 0, preorder.size() - 1, inorder,0, inorder.size()-1);
}
};