题目描述

根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
示例：

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

题目链接： https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

思路

先序序列的第一个值代表根结点的值，根据根结点的值把中序序列分成两部分，中序序列左边的代表左子树的中序序列，中序序列右边代表右子树的中序序列。根据中序序列左右子树序列的长度又可以把先序序列分成两部分，分别代表左右子树的先序序列，然后递归建树即可。代码如下：

/**
 * 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() || inorder.empty()) return nullptr;

        TreeNode* root = doBuild(preorder, inorder);
        return root;
    }

    TreeNode* doBuild(vector<int> preorder, vector<int> inorder){
        if(preorder.size()==1){
            return new TreeNode(preorder[0]);
        }
        if(preorder.size()==0) return nullptr;

        int rootVal = preorder[0];   // 根节点的额值
        int rootPos = 0;   // 中序序列中根结点的位置
        for(; rootPos<inorder.size(); rootPos++){
            if(inorder[rootPos]==rootVal) break;
        }
        int leftLen = rootPos;  // 左子树序列长度
        int rightLen = inorder.size()-rootPos;  // 右子树序列长度

        vector<int> preorderLeft(&preorder[1], &preorder[1+leftLen]); //左子树先序序列,范围[1, 1+leftLen)
        vector<int> preorderRight(&preorder[1+leftLen], &preorder[preorder.size()]); //右子树先序序列,范围[1+leftLen, 数组尾)
        vector<int> inorderLeft(&inorder[0], &inorder[rootPos]); //左子树中序序列,范围[0, rootPos)
        vector<int> inorderRight(&inorder[rootPos+1], &inorder[inorder.size()]); //右子树中序序列,范围[rootPos,数组尾) 

        TreeNode* root = new TreeNode(rootVal);
        root->left = doBuild(preorderLeft, inorderLeft);
        root->right = doBuild(preorderRight, inorderRight);
        return root;
        
    }
};

在获得 vector 子数组时用了一个小技巧，也就是使用vector<int> v(&v[m], &[n])可以获得 v 中范围为[m, n)的子数组。

• 时间复杂度：O(n)
  n 为序列长度。
• 空间复杂度：O(h)
  h 为树高。