Skip to content

105. Construct Binary Tree from Preorder and Inorder Traversal

难度: Medium

刷题内容

原题连接

  • 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 ```

解题方案

思路 1

和106思路一致
TreeNode* dfs(vector<int>& preorder, vector<int>& inorder, int start, int end, int& index){
    int post = preorder[index];
    int i=start;
    for(;i<end;i++)
        if(post == inorder[i])
            break;
    TreeNode* node = new TreeNode(post);
    if(i>start)
        node->left = dfs(preorder, inorder, start, i-1, ++index);
    if(i<end)
        node->right = dfs(preorder, inorder, i+1, end, ++index);
    return node;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    if(preorder.empty()||inorder.empty())
        return NULL;
    int index =0;
    return dfs(preorder, inorder, 0, preorder.size()-1, index);
}



回到顶部