欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

105. Construct Binary Tree from Preorder and Inorder Traversal

程序员文章站 2022-03-03 10:21:41
...

Given preorder and inorder traversal of a tree, construct the binary tree.
Note:You may assume that duplicates do not exist in the tree.

class Solution {
public:
    TreeNode* createTree(vector<int>& preorder,int pre_start,int pre_end,vector<int>& inorder,int in_start,int in_end)
    {
        if(pre_start>pre_end)
           return NULL;
        int root = preorder[pre_start];
        int index;
        for(int i=in_start;i<=in_end;i++)
        {
            if(inorder[i] == root)
              index = i;
        }
        int len = index - in_start;
        TreeNode* left = createTree(preorder,pre_start+1,pre_start+len,inorder,in_start,index-1);
        TreeNode* right = createTree(preorder,pre_start+len+1,pre_end,inorder,index+1,in_end);
        
        TreeNode* node = new TreeNode(root);
        node->left = left;
        node->right = right;
        return node;
        
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.size()==0||inorder.size()==0)
          return NULL;
        return createTree(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1);
    }
};