题目描述

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

算法

(dfs) $O(n^2)$

这个写法利用原函数 buildTree 直接递归。

1.前序遍历第一个是当前的根。
2.利用根节点，在将中序遍历分出来左子树。
3.拷贝出左子树的前序和中序数组，将左子树进行递归。
4.拷贝出右子数的前序和中序数组，将右子树进行递归。

时间复杂度分析：每次对数组的拷贝，占用了主要时间，所以复杂度$O(n^2)$

C++ 代码

/**
 * 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.size() == 0 || inorder.size() == 0) return NULL;
        TreeNode *root = new TreeNode (preorder[0]);
        int i = 0;
        vector<int> preo,ino;
        while ( inorder[i] != root->val){
            ino.push_back(inorder[i]);
            i++;
        }
        int j = 1;
        while (i > 0){
            preo.push_back(preorder[j]);
            j++;
            i--;
        }
        root->left = buildTree(preo,ino);
        vector<int> rp,rin;
        while(j < preorder.size()){
            rp.push_back(preorder[j]);
            rin.push_back(inorder[j]);
            j++;
        }
        root->right = buildTree(rp,rin);
        return root;
    }
};