Leetcode 105 Construct Binary Tree from Preorder and Inorder Traversal

triplebee

发布于 2018-01-12 14:55:43

4090

发布于 2018-01-12 14:55:43

文章被收录于专栏：计算机视觉与深度学习基础计算机视觉与深度学习基础计算机视觉与深度学习基础

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);
    }
};

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2016-10-11 ，如有侵权请联系 cloudcommunity@tencent.com 删除

duplicates