Leetcode 105 Construct Binary Tree from Preorder and Inorder Traversal

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

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

根据先序和中序遍历还原二叉树。

思路很简单,先序中的第一个点必然为root,所以只要以先序的第一个元素在中序中的位置为分界线,左边为左子树,右边为右子树,递归下去就行

然而我遇到了问题,这是第一个版本,通过MLE了,我想应该是反复开辟了新的vector空间。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.empty()) return NULL;
        TreeNode* root=new TreeNode(preorder[0]);
        int pos;
        for(int i=0;i<inorder.size();i++)
        if(inorder[i]==preorder[0]) 
        {
            pos=i;
            break;
        }
        vector<int> leftpre,leftin,rightpre,rightin;
        for(int i=0;i<pos;i++)
        {
            leftpre.push_back(preorder[i+1]);
            leftin.push_back(inorder[i]);
        }
        for(int i=pos+1;i<preorder.size();i++)
        {
            rightpre.push_back(preorder[i]);
            rightin.push_back(inorder[i]);
        }
        root->left=buildTree(leftpre,leftin);
        root->right=buildTree(rightpre,rightin);
        return root;
    }
};

如果不开辟新的vector空间,只在原来的引用上做呢?毕竟引用不会像直接定义开辟另外的空间,可以顺利通过了,丑陋的WA了好多次。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* dfs(vector<int>& preorder, int ps,int pe,vector<int>& inorder,int is,int ie)
    {
        if(ps>pe ) return NULL;
        TreeNode* root=new TreeNode(preorder[ps]);
        int pos;
        for(int i=is;;i++)
        if(inorder[i]==preorder[ps])
        {
            pos=i-is;
            break;
        }
        root->left=dfs(preorder,ps+1,ps+pos,inorder,is,is+pos-1);
        root->right=dfs(preorder,ps+pos+1,pe,inorder,is+pos+1,ie);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return dfs(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1);
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励