LeetCode-105-Construct Binary Tree from Preorder and Inorder

发布时间：2020-12-14 04:26:08 所属栏目：大数据来源：网络整理

导读：算法描述： Given preorder and inorder traversal of a tree,construct the binary tree. Note: You may assume that duplicates do not exist in the tree. For example,given preorder =?[3,9,20,15,7]inorder = [9,3,7] Return the following binary tre

算法描述：

Given preorder and inorder traversal of a tree,construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example,given

preorder =?[3,9,20,15,7]
inorder = [9,3,7]

Return the following binary tree:

    3
   /   9  20
    /     15   7

解题思路：理解原理。

    TreeNode* buildTree(vector<int>& preorder,vector<int>& inorder) {
        return helper(preorder,0,preorder.size()-1,inorder,inorder.size()-1);
    }
    
    TreeNode* helper(vector<int>& preorder,int ps,int pe,vector<int>& inorder,int is,int ie){
        if(ps > pe || is > ie) return nullptr;
        TreeNode* node = new TreeNode(preorder[ps]);
        int pos = 0;
        for(int i=is; i <= ie; i++){
            if(inorder[i]==preorder[ps]){
                pos = i;
                break;
            }
        }
        
        node->left = helper(preorder,ps+1,pe,is,pos-1);
        node->right = helper(preorder,ps+pos-is+1,pos+1,ie);
        return node;
    }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!